A185101 The number n written using the minimum number of terms in the base where the values of the places are 1 and primes (noncomposites). For multiple solutions the smallest binary value is chosen.

0, 1, 10, 100, 101, 1000, 1001, 10000, 1100, 10010, 10100, 100000, 11000, 1000000, 100100, 1000010, 101000, 10000000, 110000, 100000000, 1010000, 100000010, 10001000, 1000000000, 1100000, 1000000010, 100010000, 1100100, 10100000, 10000000000

Offset: 0

Author

Frank M Jackson, Jan 23 2012

Keywords

• nonn

Comments

There are many ways of generating binary vectors a(n) for selecting noncomposites that when summed give n. A007924 uses the greedy algorithm. The above sequence uses the strong Goldbach conjecture that any integer is the sum of at most three distinct summands. It generates a(n) to select the minimum number of distinct noncomposites. Where there are multiple solutions, it chooses the smallest binary vector.

Examples

			n=57 which is > 6 and odd, so m = (nextprime > 57/3) = 23 and n-m = 34 is even, thus A082467(17) = 6 and algorithm selects {23,11,23}. These are not distinct primes, so m = nextprime(nextprime > n/3) = 29 and A082467(14)=3, thus a(n) selects {29,11,17} as the binary vector 10010100000.
		

Links

• Eric Weisstein's World of Mathematics, Goldbach Conjecture.

Crossrefs

Cf. A007924, A066352, A200947.

Programs

Mathematica

nextprime[j_] := Module[{k}, If[j==0, 1, (k=Floor[j]+1; While[!PrimeQ[k], k++]; k)]]; primetable[n_] := Module[{p, q}, Which[n==1, {0, 2, 0}, n==2, {1, 3, 0}, n==3, {1, 5, 0}, True, (p=n+1; q=2n-p; While[q>0&&!(PrimeQ[p]&&PrimeQ[q]), p++; q--]; {0, q, p})]]; fintable[m_] := Module[{temptable}, Which[m==0, {0, 0, 0}, m==1, {1, 0, 0}, PrimeQ[m], {0, m, 0}, PrimeQ[m-2]&&m>4, {0, 2, m-2}, EvenQ[m], primetable[m/2], True, (temptable=primetable[(m-nextprime[m/3])/2]; If[temptable[[3]]==nextprime[m/3], (temptable=primetable[(m-nextprime[nextprime[m/3]])/2]; temptable[[1]]=nextprime[nextprime[m/3]]), temptable[[1]]=nextprime[m/3]]; temptable)]]; decimal[t_] := Module[{temp2table, tempdecimal=0}, (temp2table=fintable[t]; If[temp2table[[1]]==0, Null, tempdecimal=tempdecimal+2^PrimePi[temp2table[[1]]]]; If[temp2table[[2]]==0, Null, tempdecimal=tempdecimal+2^PrimePi[temp2table[[2]]]]; If[temp2table[[3]]==0, Null, tempdecimal=tempdecimal+2^PrimePi[temp2table[[3]]]];tempdecimal)];Table[IntegerString[decimal[i], 2], {i, 0, 100}]

Formula

For n, 1 to 6, a(n) is manually defined. For n prime, a(n) selects n. For n > 6 and n-2 prime, a(n) selects 2 and n-2. For n > 6 and even, use A082467(n/2) to give k, then a(n) selects n/2+k, n/2-k. For n>6 and odd, let m = (nextprime > n/3), then n-m is even and A082467((n-m)/2) gives k, a(n) selects m, (n-m)/2-k, (n-m)/2+k. If m = (n-m)/2+k, then m = nextprime(nextprime > n/3) and repeat.

Extensions

Name clarified by Frank M Jackson, Oct 08 2013