cp's OEIS Frontend

A225099 Number of ways n can be represented as a sum of two distinct nontrivial prime powers (numbers of the form p^k where p is a prime number and k >= 2).

%I A225099 #14 Apr 29 2013 16:43:26
%S A225099 0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,1,0,0,1,0,0,0,1,1,0,0,0,1,0,1,0,1,
%T A225099 1,1,2,0,0,0,1,2,0,1,0,0,0,0,1,0,0,0,1,1,0,0,0,2,1,1,0,0,0,0,0,1,0,0,
%U A225099 1,0,0,0,1,1,1,0,1,0,0,0,1,1,0,0,0,1,0,0,0,2
%N A225099 Number of ways n can be represented as a sum of two distinct nontrivial prime powers (numbers of the form p^k where p is a prime number and k >= 2).
%C A225099 Nontrivial prime powers are A025475 except the first term A025475(1) = 1.
%C A225099 First occurrences of terms bigger than 2: see A225100.
%C A225099 Among first 2^32 terms 16346685 are positive (that is 0.38%).
%C A225099 Among first 2^34 terms 55527808 are positive (0.32%).
%e A225099 12 = 2^2 + 2^3, so a(12) = 1.
%e A225099 36 = 32 + 4 = 27 + 9, so a(36) = 2.
%t A225099 nn = 100; p = Sort[Flatten[Table[Prime[n]^i, {n, PrimePi[Sqrt[nn]]}, {i, 2, Log[Prime[n], nn]}]]]; t =Sort[Select[Flatten[Table[p[[i]] + p[[j]], {i, Length[p] - 1}, {j, i + 1, Length[p]}]], # <= nn &]]; Table[Count[t, n], {n, 0, nn}] (* _T. D. Noe_, Apr 29 2013 *)
%o A225099 (C)
%o A225099 #include <stdio.h>
%o A225099 #include <stdlib.h>
%o A225099 #define TOP (1ULL<<17)
%o A225099 unsigned long long *powers, pwFlat[TOP], primes[TOP] = {2};
%o A225099 int main() {
%o A225099   unsigned long long a, c, i, j, k, n, p, r, pp = 1, pfp = 0;
%o A225099   powers = (unsigned long long*)malloc(TOP * TOP/8);
%o A225099   memset(powers, 0, TOP * TOP/8);
%o A225099   for (a = 3; a < TOP; a += 2) {
%o A225099     for (p = 0; p < pp; ++p)  if (a % primes[p] == 0) break;
%o A225099     if (p == pp)  primes[pp++] = a;
%o A225099   }
%o A225099   for (k = i = 0; i < pp; ++i)
%o A225099     for (j = primes[i]*primes[i]; j < TOP*TOP; j *= primes[i])
%o A225099       powers[j/64] | = 1ULL << (j & 63), ++k;
%o A225099   if (k > TOP) exit(1);
%o A225099   for (n = 0; n < TOP * TOP; ++n)
%o A225099     if (powers[n/64] & (1ULL << (n & 63)))  pwFlat[pfp++] = n;
%o A225099   for (n = 0; n < TOP * TOP; ++n) {
%o A225099     for (c = i = 0; pwFlat[i] * 2 < n; ++i)
%o A225099       r=n-pwFlat[i], c+= (powers[r/64] & (1ULL <<(r&63))) > 0;
%o A225099     printf("%llu, ", c);
%o A225099   }
%o A225099   return 0;
%o A225099 }
%Y A225099 Cf. A025475, A225100.
%K A225099 nonn
%O A225099 0,37
%A A225099 _Alex Ratushnyak_, Apr 27 2013