A225927 - OEIS

A225927

Least number of prime powers greater than 1 needed to sum up to n, or 0 if n cannot be represented as a sum of prime powers.

0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 2, 2, 0, 0, 1, 2, 2, 0, 2, 3, 3, 0, 2, 1, 3, 1, 3, 2, 4, 2, 1, 2, 2, 2, 2, 3, 3, 3, 2, 2, 3, 2, 3, 3, 4, 3, 2, 1, 2, 3, 2, 2, 2, 4, 3, 2, 2, 2, 3, 3, 3, 3, 1, 2, 3, 3, 2, 3, 3, 4, 2, 2, 2, 3, 2, 3, 3, 3, 2, 1, 3, 3, 3, 2, 3, 4, 3, 2, 2

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,12

COMMENTS

Nontrivial prime powers: A025475 except 1.

LINKS

Table of n, a(n) for n=1..90.

EXAMPLE

26 = 9 + 9 + 8, three summands, so a(26) = 3.

PROG

(C)

#include <stdio.h> // GCC -O3

#define TOP (1ULL<<15) // ~140 seconds // (1ULL<<17) is ok

#define TOP2 (TOP*TOP)

typedef unsigned long long U64;

int compare64(const void *p1, const void *p2) {

if (*(U64*)p1 < *(U64*)p2) return -1;

return (*(U64*)p1 == *(U64*)p2) ? 0 : 1;

}

int main() {

U64 i, j, k, p, pp=1, pfp=0, *primes, *pwFlat = (U64*)malloc(TOP*2);

primes = (U64*)malloc(TOP2);

char *c = (char*)pwFlat, *f = (char*)primes, *ff;

memset(c, 0, TOP);

for (primes[0]=2, i=3; i<TOP; i+=2) if (c[i>>1]==0)

for (primes[pp++]=i, j=i*i>>1; j<TOP/2; j+=i) c[j]=1;

for (i = 0; i < pp; ++i)

for (j=primes[i]*primes[i]; j<TOP2; j*=primes[i]) pwFlat[pfp++]=j;

qsort(pwFlat, pfp, 8, compare64);

memset(f, 100, TOP2);

for (pwFlat[pfp]=TOP2, i=0; (p=pwFlat[i])<TOP2; printf("."), ++i)

for(f[p]=1, j=0; j<=i && (pp=p+pwFlat[j])<TOP2; ++j)

for(f[pp]=2, k=0; k<=j && (pfp=pp+pwFlat[k])<TOP2; ++k) f[pfp]=3;

for (k=1; k < TOP2; k++) {

if (f[k]==100) {

for (j=0, ff=&f[k], pp=99; (p=pwFlat[j]) < k; j++)

if (ff[-p] < pp) { pp = ff[-p]; if (pp<=3) break; }

f[k] = pp+1;

}

if (k<200) printf("%llu, ", f[k] > 99 ? 0 : f[k]);

else if (f[k]>4) printf("\n%llu at %llu ", f[k], k);

}

return 0;

}

CROSSREFS

Cf. A025475, A225926.

Sequence in context: A328802 A355245 A103822 * A029392 A035379 A280452

Adjacent sequences: A225924 A225925 A225926 * A225928 A225929 A225930

KEYWORD

nonn

AUTHOR

Alex Ratushnyak, May 21 2013

STATUS

approved