A211681 Numbers such that all the substrings of length <= 2 are primes.

2, 3, 5, 7, 23, 37, 53, 73, 237, 373, 537, 737, 2373, 3737, 5373, 7373, 23737, 37373, 53737, 73737, 237373, 373737, 537373, 737373, 2373737, 3737373, 5373737, 7373737, 23737373, 37373737, 53737373, 73737373, 237373737, 373737373, 537373737, 737373737

Offset: 1

Author

Hieronymus Fischer, Apr 30 2012

Keywords

• nonn
• base
• easy

Comments

The terms are primes for n = 1, 2, 3, 4, 5, 6, 7, 8, 10, 21, 23, 27, 31, 43, 45, 60, 67, 82, 91, .... The further terms until index 102 are composite. For the subsequence with prime terms see A211682. - [updated by Hieronymus Fischer, Oct 02 2018]

From Hieronymus Fischer, Oct 02 2018: (Start)

For indices n > 8, prime terms satisfy n mod 24 = 1, 3, 5, 7, 10, 12, 19, 21, 23. However, this condition is not sufficient. Indeed, for n <= 200 most of those terms are proven composite unless the terms with n = 103, 106, 123, 156, 165, 175, 178, 191, 193 and 195 which are potentially prime.

The terms are composite for n > 10 and n mod 24 = 0, 2, 4, 6, 8, 9, 11, 13, 14, 15, 16, 17, 18, 20, 22 (see formula section for the details).

(End)

Cf. A213299 for the partial sums.

Examples

			a(11)=537, since all substrings of length <= 2 are primes (5, 3, 7, 53 and 37).
a(21)=237373, the substrings of length <= 2 are 2, 3, 7, 23, 37, 73.
		

Links

• Hieronymus Fischer, Table of n, a(n) for n = 1..250
• Index entries for linear recurrences with constant coefficients, signature (1,0,0,9,-9,0,0,10,-10).

Crossrefs

Cf. A019546, A035232, A039996, A046034, A085823, A211682, A213299.

Programs

Mathematica

Table[FromDigits/@Select[Tuples[{2,3,5,7},n],AllTrue[FromDigits/@ Partition[ #,2,1],PrimeQ]&],{n,9}]//Flatten (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, Jun 13 2020 *)

Formula

a(1+8*k) = 2*10^(2k) + 37*(10^(2k)-1)/99,

a(2+8*k) = 3*10^(2k) + 73*(10^(2k)-1)/99,

a(3+8*k) = 5*10^(2k) + 37*(10^(2k)-1)/99,

a(4+8*k) = 7*10^(2k) + 37*(10^(2k)-1)/99,

a(5+8*k) = 23*10^(2k) + 73*(10^(2k)-1)/99,

a(6+8*k) = 37*10^(2k) + 37*(10^(2k)-1)/99,

a(7+8*k) = 53*10^(2k) + 73*(10^(2k)-1)/99,

a(8+8*k) = 73*10^(2k) + 73*(10^(2k)-1)/99, for k >= 0.

a(n) = ((2*n+7) mod 8 + dn3 - dn2)*10^dn_1 + floor((37+36*(dn2-dn1))*10^dn_1/99), where dn1 = floor((n+1)/4), dn2 = floor((n+2)/4), dn3 = floor((n+3)/4), dn_1 = floor((n-1)/4). [updated by Hieronymus Fischer, Oct 02 2018]

From Hieronymus Fischer, Oct 02 2018: (Start)

a(24k + 0) = 73*(10^(6k-2) + (10^(6k-2)-1)/99), for k > 0.

a(24k + 2) = 3*(1245790*(10^(6k)-1)/999999 + 1),

a(24k + 4) = 7*(1053390*(10^(6k)-1)/999999 + 1),

a(24k + 6) = 37*(10^(6k) + (10^(6k)-1)/99),

a(24k + 8) = 73*(10^(6k) + (10^(6k)-1)/99),

a(24k + 9) = 3*(79124500*(10^(6k)-1)/999999 + 79),

a(24k + 11) = 3*(79124500*(10^(6k)-1)/999999 + 79 + 10^(6k+2)),

a(24k + 13) = 3*(791245000*(10^(6k)-1)/999999 + 791),

a(24k + 14) = 37*(10^(6k+2) + (10^(6k+2)-1)/99),

a(24k + 15) = 3*(791245000*(10^(6k)-1)/999999 + 791 + 10^(6k+3)),

a(24k + 16) = 73*(10^(6k+2) + (10^(6k+2)-1)/99),

a(24k + 17) = 7*(3391050000*(10^(6k)-1)/999999 + 3391),

a(24k + 18) = 7*(5339100000*(10^(6k)-1)/999999 + 5339),

a(24k + 20) = 3*(24579100000*(10^(6k)-1)/999999 + 24579),

a(24k + 22) = 37*(10^(6k+4) + (10^(6k+4)-1)/99), for k >= 0.

(End)

Recursion for n>8:

a(n) = 10*(1+a(n-4)) - a(n-4) mod 10.

G.f.: (2*x*(1+x^10) + 3*x^2*(1 + x^3 + x^5 + x^6) + 5*x^3*(1+x^6) + 7*x^4*(1+x^2))/((1-10*x^4)*(1-x^8)). [corrected by Hieronymus Fischer, Sep 03 2012]

From Chai Wah Wu, Feb 08 2023: (Start)

a(n) = a(n-1) + 9*a(n-4) - 9*a(n-5) + 10*a(n-8) - 10*a(n-9) for n > 9.

G.f.: x*(2*x^7 - 2*x^6 + 5*x^5 - 2*x^4 + 2*x^3 + 2*x^2 + x + 2)/((x - 1)*(x^4 + 1)*(10*x^4 - 1)). (End)