A228018 - OEIS

%I #21 Sep 18 2024 08:43:35

%S 9,49,243,961,16129,67092481,17179607041,274876858369,

%T 4611686014132420609

%N Prime powers p (A025475) such that the sum of the proper divisors of p is also a prime power.

%C Numbers k such that both k and A001065(k) are in A025475.

%C Eight of the first nine terms are squares of Mersenne primes (A133049).

%C From _Pontus von Brömssen_, Sep 17 2024: (Start)

%C All squares of Mersenne primes are terms.

%C 10^20 < a(10) <= A133049(9) = (2^61-1)^2.

%C All terms are odd. Otherwise, 2^k would be a term for some positive k >= 2 and then A001065(2^k) = 2^k-1 would be a prime power in A025475, which is impossible by Catalan's conjecture (Mihăilescu's theorem).

%C (End)

%e Proper divisors of 243 are 1, 3, 9, 27, 81, their sum is 121 = 11^2, so 243 is in the sequence.

%o (C)

%o #include <stdio.h>

%o #include <stdlib.h>

%o #define TOP (1ULL<<32)

%o typedef unsigned long long U64;

%o int compare64(const void *p1, const void *p2) {

%o   if (*(U64*)p1== *(U64*)p2) return 0;

%o   return (*(U64*)p1 < *(U64*)p2) ? -1 : 1;

%o }

%o U64 findElement(U64 *a, U64 start, U64 end, U64 element) {

%o   if (start+1==end)  return (a[start]==element);

%o   U64 mid = (start+end)/2;

%o   if (a[mid] > element)

%o     return findElement(a, start, mid, element);

%o   return findElement(a, mid, end, element);

%o }

%o int main() {

%o   U64 i, j, p, n=0, *pp = (U64*)malloc(TOP/2), sum;

%o   unsigned char *c = (unsigned char *)malloc(TOP/16);

%o   if (!c || !pp) exit(1);

%o   memset(c, 0, TOP/16);

%o   pp[n++] = 1;

%o   for (i=1; i < TOP; i+=2) {

%o     if ((c[i>>4] & (1<<((i>>1) & 7)))==0) {

%o       for (p=i+(i==1), j = p*p; ; j*=p) {

%o         pp[n++] = j;

%o         double k = ((double)j) * ((double)p);

%o         if (k >= ((double)(1ULL<<60)*16.0)) break;

%o       }

%o       if (i>1)

%o         for (j=i*i>>1; j<TOP/2; j+=i)  c[j>>3] |= 1<<(j&7);

%o     }

%o     if ((i&(i-2))==1)  printf("%llu ", i);

%o   }

%o   printf("// %llu\n\n", n);

%o   qsort(pp, n, 8, compare64);

%o   for (i=1; i < TOP; i+=2)

%o     if ((c[i>>4] & (1<<((i>>1) & 7)))==0)

%o       for (p=i+(i==1), sum=1+p, j = p*p; ; j*=p) {

%o         if (findElement(pp, 0, n, sum)) printf("%llu, ", j);

%o         sum += j;

%o         double k = ((double)j) * ((double)p);

%o         if (k >= ((double)(1ULL<<60)*16.0)) break;

%o       }

%o   return 0;

%o }

%o (PARI) for(n=1,10^6,if(!isprime(n),v=factor(n);if(matsize(v)[1]==1,s=sumdiv(n,d,d)-n;if(!isprime(s),vv=factor(s);if(matsize(vv)[1]==1,print(n)))))) /* _Ralf Stephan_, Aug 05 2013 */

%Y Cf. A025475, A001065, A133049.

%K nonn,more

%O 1,1

%A _Alex Ratushnyak_, Aug 02 2013