A316412 - OEIS

%I #37 Sep 23 2018 22:53:01

%S 1,2,3,5,7,11,13,17,23,31,37,53,71,73,113,131,137,173,311,317

%N Positive numbers m so that deletion of some or none but not all digits from m yields a noncomposite number.

%C Subsequence of A068669. It is easy to see that these are the only terms from the said sequence that satisfy our definition; there are no more terms < 10000. If there is one >= 10000 then there would be one in [1000, 9999]. A contradiction hence the sequence is finite and full.

%C Also noncomposites m (in base 10) for which the concatenation of every subsequence of digits of m is noncomposite (in base 10). - _David A. Corneth_, Aug 08 2018

%e 317 is a member since all its subsequences, i.e., 3, 1, 7, 31, 17, 37, 317, are noncomposite.

%e 313 is not a member since one of its subsequences (33) is composite.

%t Select[Range[10^3], AllTrue[FromDigits /@ Union@ Rest@ Subsets@ IntegerDigits@ #, ! CompositeQ@ # &] &] (* _Michael De Vlieger_, Aug 05 2018 *)

%o (C++)

%o #include <iostream>

%o #include <queue>

%o int main() {

%o     int upper = 1000;

%o     // 0->composite, 1->prime, 2->member of the sequence

%o     auto *nums = new int[upper];

%o     for (int i = 0; i < upper; i++)

%o         nums[i] = 1;

%o     nums[0] = nums[1] = 2;

%o     std::queue<int> in_progress;

%o     in_progress.push(1);

%o     for (int i = 2; i < upper; i++) {

%o         if (nums[i] == 0) continue;

%o         // is a prime

%o         in_progress.push(i);

%o         for (int j = i + i; j < upper; j += i) {

%o             nums[j] = 0;

%o         }

%o     }

%o     while (!in_progress.empty()) {

%o         int p = in_progress.front();

%o         in_progress.pop();

%o         int div = 1;

%o         bool valid = true;

%o         while (div <= p) {

%o             int del = (p / (div * 10)) * div + (p % div);

%o             if (nums[del] != 2) {

%o                 valid = false;

%o                 break;

%o             }

%o             div *= 10;

%o         }

%o         if (valid) {

%o             nums[p] = 2;

%o             std::cout << p << ", ";

%o         }

%o     }

%o }

%Y Subsequence of A068669.

%Y Cf. A008578.

%K base,easy,fini,full,nonn

%O 1,2

%A _Matej Kripner_, Aug 04 2018