cp's OEIS Frontend

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

%I A316412 #37 Sep 23 2018 22:53:01
%S A316412 1,2,3,5,7,11,13,17,23,31,37,53,71,73,113,131,137,173,311,317
%N A316412 Positive numbers m so that deletion of some or none but not all digits from m yields a noncomposite number.
%C A316412 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 A316412 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 A316412 317 is a member since all its subsequences, i.e., 3, 1, 7, 31, 17, 37, 317, are noncomposite.
%e A316412 313 is not a member since one of its subsequences (33) is composite.
%t A316412 Select[Range[10^3], AllTrue[FromDigits /@ Union@ Rest@ Subsets@ IntegerDigits@ #, ! CompositeQ@ # &] &] (* _Michael De Vlieger_, Aug 05 2018 *)
%o A316412 (C++)
%o A316412 #include <iostream>
%o A316412 #include <queue>
%o A316412 int main() {
%o A316412     int upper = 1000;
%o A316412     // 0->composite, 1->prime, 2->member of the sequence
%o A316412     auto *nums = new int[upper];
%o A316412     for (int i = 0; i < upper; i++)
%o A316412         nums[i] = 1;
%o A316412     nums[0] = nums[1] = 2;
%o A316412     std::queue<int> in_progress;
%o A316412     in_progress.push(1);
%o A316412     for (int i = 2; i < upper; i++) {
%o A316412         if (nums[i] == 0) continue;
%o A316412         // is a prime
%o A316412         in_progress.push(i);
%o A316412         for (int j = i + i; j < upper; j += i) {
%o A316412             nums[j] = 0;
%o A316412         }
%o A316412     }
%o A316412     while (!in_progress.empty()) {
%o A316412         int p = in_progress.front();
%o A316412         in_progress.pop();
%o A316412         int div = 1;
%o A316412         bool valid = true;
%o A316412         while (div <= p) {
%o A316412             int del = (p / (div * 10)) * div + (p % div);
%o A316412             if (nums[del] != 2) {
%o A316412                 valid = false;
%o A316412                 break;
%o A316412             }
%o A316412             div *= 10;
%o A316412         }
%o A316412         if (valid) {
%o A316412             nums[p] = 2;
%o A316412             std::cout << p << ", ";
%o A316412         }
%o A316412     }
%o A316412 }
%Y A316412 Subsequence of A068669.
%Y A316412 Cf. A008578.
%K A316412 base,easy,fini,full,nonn
%O A316412 1,2
%A A316412 _Matej Kripner_, Aug 04 2018