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

Offset: 1

Author

Alex Ratushnyak, May 21 2013

Keywords

• nonn

Comments

Nontrivial prime powers: A025475 except 1.

Examples

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

Crossrefs

Cf. A025475, A225926.

Programs

C

#include       // 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>1]==0)
    for (primes[pp++]=i, j=i*i>>1; j 99 ? 0 : f[k]);
      else if (f[k]>4)  printf("\n%llu at %llu   ", f[k], k);
  }
  return 0;
}