A225926 Least number of prime powers needed to sum up to n.

1, 2, 3, 1, 2, 3, 4, 1, 1, 2, 3, 2, 2, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 1, 2, 1, 2, 2, 3, 2, 1, 2, 2, 2, 2, 3, 3, 3, 2, 2, 3, 2, 3, 3, 4, 3, 2, 1, 2, 3, 2, 2, 2, 3, 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, 2, 3, 3, 2, 3, 4, 3, 2, 2

Offset: 1

Author

Alex Ratushnyak, May 21 2013

Keywords

• nonn

Comments

Prime powers: A025475, which includes 1 because it includes the power 0, but excludes power 1.

Not necessarily distinct prime powers, see example for a(2).

Terms bigger than 4: a(340473) = a(3881313) = 5, and the next term, if it exists, has index bigger than 2^34.

Examples

			2 = 1 + 1, two summands, so a(2) = 2.
26 = 25 + 1, two summands, so a(26) = 2.
		

Crossrefs

Cf. A025475, A225927.

Programs

C

#include       // GCC -O3
#define TOP (1ULL<<15)  // ~130 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; j4)  printf("\n%llu at %llu   ", f[k], k);
  }
  return 0;
}