OFFSET
1,1
COMMENTS
Subsequence of A226230.
EXAMPLE
125 = 4 + 11^2 = 25 + 10^2 = 121 + 4^2. Because there are three representations, 125 is in the sequence. Note that 100 + 5^2 is not listed, because 100 is not a prime power.
PROG
(C)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define TOP (1ULL<<32)
typedef unsigned long long U64;
int compare64(const void *p1, const void *p2) {
if (*(U64*)p1== *(U64*)p2) return 0;
return (*(U64*)p1 < *(U64*)p2) ? -1 : 1;
}
int main() {
U64 i, j, k, p, t, r, n=0, *pp = (U64*)malloc(TOP/2);
unsigned char *c = (unsigned char *)malloc(TOP/8);
memset(c, 0, TOP/8);
for (pp[n++] = i = 1; i < TOP; i+=2)
if ((c[i>>4] & (1<<((i>>1) & 7)))==0) {
for (p=i+(i==1), j = p*p; ; j*=p) {
pp[n++] = j;
double k = ((double)j) * ((double)p);
if (k >= ((double)(1ULL<<62)*4.0)) break;
}
if(i>1) for (j=i*i>>1; j<TOP; j+=i) c[j>>3]|= 1<<(j&7);
}
qsort(pp, n, 8, compare64);
for (i = 0; i < n; i++)
for (p=pp[i], j = k = 0; j < i; j++) {
t = p - pp[j];
r = sqrt(t);
if (r*r==t && ++k==2) { printf("%llu, ", p); break; }
}
return 0;
}
CROSSREFS
KEYWORD
nonn
AUTHOR
Alex Ratushnyak, May 31 2013
STATUS
approved