cp's OEIS Frontend

A226231 Nontrivial prime powers (A025475) which are a sum of a smaller nontrivial prime power and a perfect square in more than 1 way.

%I A226231 #10 Jun 06 2013 19:13:27
%S A226231 25,125,512,3125,4913,50653,78125,7645373,48828125,69343957,310288733,
%T A226231 410338673,1220703125,4103684801,24820429213,164296466333,
%U A226231 296709280757,762939453125,1772000266301,10368641602001,11392143817501,19073486328125,29724740184833,72079590632113
%N A226231 Nontrivial prime powers (A025475) which are a sum of a smaller nontrivial prime power and a perfect square in more than 1 way.
%C A226231 Subsequence of A226230.
%e A226231 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.
%o A226231 (C)
%o A226231 #include <stdio.h>
%o A226231 #include <stdlib.h>
%o A226231 #include <math.h>
%o A226231 #define TOP (1ULL<<32)
%o A226231 typedef unsigned long long U64;
%o A226231 int compare64(const void *p1, const void *p2) {
%o A226231   if (*(U64*)p1== *(U64*)p2) return 0;
%o A226231   return (*(U64*)p1 < *(U64*)p2) ? -1 : 1;
%o A226231 }
%o A226231 int main() {
%o A226231   U64 i, j, k, p, t, r, n=0, *pp = (U64*)malloc(TOP/2);
%o A226231   unsigned char *c = (unsigned char *)malloc(TOP/8);
%o A226231   memset(c, 0, TOP/8);
%o A226231   for (pp[n++] = i = 1; i < TOP; i+=2)
%o A226231     if ((c[i>>4] & (1<<((i>>1) & 7)))==0) {
%o A226231       for (p=i+(i==1), j = p*p; ; j*=p) {
%o A226231         pp[n++] = j;
%o A226231         double k = ((double)j) * ((double)p);
%o A226231         if (k >= ((double)(1ULL<<62)*4.0)) break;
%o A226231       }
%o A226231       if(i>1) for (j=i*i>>1; j<TOP; j+=i)  c[j>>3]|= 1<<(j&7);
%o A226231     }
%o A226231   qsort(pp, n, 8, compare64);
%o A226231   for (i = 0; i < n; i++)
%o A226231     for (p=pp[i], j = k = 0; j < i; j++) {
%o A226231       t = p - pp[j];
%o A226231       r = sqrt(t);
%o A226231       if (r*r==t && ++k==2) { printf("%llu, ", p); break; }
%o A226231     }
%o A226231   return 0;
%o A226231 }
%Y A226231 Cf. A025475, A226230, A226232.
%K A226231 nonn
%O A226231 1,1
%A A226231 _Alex Ratushnyak_, May 31 2013