Sci Advisor
HW Helper
P: 4,301

Quote by almahed
compuchip, could you write an algoritm that expresse a prime as a sum of the minor prime possible and powers of two?

Sure I will do that, if it makes you happy
Quote by Dodo
The minor prime possible is always 3 (or 2, if you allow 2^0), since the difference between 3 and the prime (or any positive integer, for that matter) can be expressed (uniquely) as a sum of powers of two; think of its binary representation.

This gives for the first 100 primes
{5,{1}}
{7,{2}}
{11,{3}}
{13,{3,1}}
{17,{3,2,1}}
{19,{4}}
{23,{4,2}}
{29,{4,3,1}}
{31,{4,3,2}}
{37,{5,1}}
{41,{5,2,1}}
{43,{5,3}}
{47,{5,3,2}}
{53,{5,4,1}}
{59,{5,4,3}}
{61,{5,4,3,1}}
{67,{6}}
{71,{6,2}}
{73,{6,2,1}}
{79,{6,3,2}}
{83,{6,4}}
{89,{6,4,2,1}}
{97,{6,4,3,2,1}}
{101,{6,5,1}}
{103,{6,5,2}}
{107,{6,5,3}}
{109,{6,5,3,1}}
{113,{6,5,3,2,1}}
{127,{6,5,4,3,2}}
{131,{7}}
{137,{7,2,1}}
{139,{7,3}}
{149,{7,4,1}}
{151,{7,4,2}}
{157,{7,4,3,1}}
{163,{7,5}}
{167,{7,5,2}}
{173,{7,5,3,1}}
{179,{7,5,4}}
{181,{7,5,4,1}}
{191,{7,5,4,3,2}}
{193,{7,5,4,3,2,1}}
{197,{7,6,1}}
{199,{7,6,2}}
{211,{7,6,4}}
{223,{7,6,4,3,2}}
{227,{7,6,5}}
{229,{7,6,5,1}}
{233,{7,6,5,2,1}}
{239,{7,6,5,3,2}}
{241,{7,6,5,3,2,1}}
{251,{7,6,5,4,3}}
{257,{7,6,5,4,3,2,1}}
{263,{8,2}}
{269,{8,3,1}}
{271,{8,3,2}}
{277,{8,4,1}}
{281,{8,4,2,1}}
{283,{8,4,3}}
{293,{8,5,1}}
{307,{8,5,4}}
{311,{8,5,4,2}}
{313,{8,5,4,2,1}}
{317,{8,5,4,3,1}}
{331,{8,6,3}}
{337,{8,6,3,2,1}}
{347,{8,6,4,3}}
{349,{8,6,4,3,1}}
{353,{8,6,4,3,2,1}}
{359,{8,6,5,2}}
{367,{8,6,5,3,2}}
{373,{8,6,5,4,1}}
{379,{8,6,5,4,3}}
{383,{8,6,5,4,3,2}}
{389,{8,7,1}}
{397,{8,7,3,1}}
{401,{8,7,3,2,1}}
{409,{8,7,4,2,1}}
{419,{8,7,5}}
{421,{8,7,5,1}}
{431,{8,7,5,3,2}}
{433,{8,7,5,3,2,1}}
{439,{8,7,5,4,2}}
{443,{8,7,5,4,3}}
{449,{8,7,5,4,3,2,1}}
{457,{8,7,6,2,1}}
{461,{8,7,6,3,1}}
{463,{8,7,6,3,2}}
{467,{8,7,6,4}}
{479,{8,7,6,4,3,2}}
{487,{8,7,6,5,2}}
{491,{8,7,6,5,3}}
{499,{8,7,6,5,4}}
{503,{8,7,6,5,4,2}}
{509,{8,7,6,5,4,3,1}}
{521,{9,2,1}}
{523,{9,3}}
{541,{9,4,3,1}}
where a line like
{491,{8,7,6,5,3}}
should be read as
[tex]491  3 = 2^8 + 2^7 + 2^6 + 2^5 + 2^3[/tex].
In the attachment I have plotted the occurring powers for the first 1000 primes (except 2 and 3). Have fun
PS the Mathematica code, in case anyone wants to reproduce this
FindPowers[n_] := Module[{m = n  3, result = {}},
While[m > 0, AppendTo[result, Floor[Log[2, m]]]; m = 2^Floor[Log[2, m]]];
result
]
ListPlot[
Function[{number, powers}, {number, #} & /@ powers] @@@ Table[{n, FindPowers[Prime[n]]}, {n, 3, 1000}],
Ticks > {Automatic, Range[0, 12]}
]
