0,3

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.

Eric Weisstein's World of Mathematics, Goldbach Conjecture.

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.

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.

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}]

Cf. A007924, A066352, A200947.

Sequence in context: A014417 A211027 A328072 * A007924 A115794 A105424

Adjacent sequences: A185098 A185099 A185100 * A185102 A185103 A185104

Frank M Jackson, Jan 23 2012

Name clarified by Frank M Jackson, Oct 08 2013

approved