login
Composite numbers k such that for all primes p dividing k, p-1 divides k-1 and p+1 divides k+1.
3

%I #46 Nov 05 2023 17:42:30

%S 8,27,32,125,128,243,343,512,1331,2048,2187,2197,3125,4913,6859,8192,

%T 12167,16807,19683,24389,29791,32768,50653,68921,74431,78125,79507,

%U 103823,131072,148877,161051,177147,205379,226981,300763,357911,371293,389017,493039,524288

%N Composite numbers k such that for all primes p dividing k, p-1 divides k-1 and p+1 divides k+1.

%C Intersection of A080062 and A056729.

%C Mainly odd powers of a prime: A056824 is a subset of this sequence.

%C If the additional limitations p-2|n-2 and p+2|n+2 should be added, only 243, 19683, 78125, 1594323 would be terms of the sequence for n <= 10^7.

%C Terms that are not perfect powers are 31*7^4, 31^3*7^4, 71*11^6, .... - _Altug Alkan_, May 17 2018

%C It appears that this is the intersection of A002808 and A171561. - _Michel Marcus_, May 19 2018

%C From _Robert Israel_, May 25 2018: (Start)

%C If i is odd and 4|j, then 31^i*7^j is a member.

%C If i is odd and 6|j, then 71^i*11^j is a member.

%C If i is odd and 12|j, then 17^i*5^j is a member.

%C If i is odd and 36|j, then 53^i*5^j is a member.

%C If i == 9 (mod 18) and 6|j, then 13^i*37^j is a member.

%C If i == 9 (mod 18) and 12|j, then 29^i*53^j is a member.

%C If i == 18 (mod 36), j == 3 (mod 6) and k == 2 (mod 4), then 5^i*17^j*53^k is a member.

%C (End)

%C Composite numbers k such that for all primes p dividing k, p+1 divides k-1 and p-1 divides k+1 are the union of 2^2j and 3^2j, with j>0. - _Paolo P. Lava_, May 16 2019

%H Giovanni Resta, <a href="/A304291/b304291.txt">Table of n, a(n) for n = 1..1000</a> (first 192 terms from Robert Israel)

%e Prime factors of 74431 are 7 and 31 and (74431-1)/(7-1) = 12405, (74431-1)/(31-1) = 2481, (74431+1)/(7+1) = 9304, (74431+1)/(31+1) = 2326.

%p with(numtheory): P:=proc(q) local a,b,k,n,ok;

%p for n from 2 to q do if not isprime(n) then a:=factorset(n); ok:=1;

%p for k from 1 to nops(a) do if frac((n-1)/(a[k]-1))>0 or frac((n+1)/(a[k]+1))>0 then ok:=0; break; fi; od;

%p if ok=1 then print(n); fi; fi; od; end: P(10^6);

%t Select[Range[4, 2^19], Function[k, And[CompositeQ@ k, AllTrue[FactorInteger[k][[All, 1]], And[Mod[k - 1, # - 1] == 0, Mod[k + 1, # + 1] == 0] &]]]] (* _Michael De Vlieger_, May 22 2018 *)

%o (PARI) lista(nn) = {forcomposite(c=1, nn, my(f = factor(c)); ok = 1; for (k=1, #f~, my(p = f[k,1]); if (((c-1) % (p-1)) || ((c+1) % (p+1)), ok = 0; break);); if (ok, print1(c, ", ")););} \\ _Michel Marcus_, May 19 2018

%o (Magma) sol:=[]; m:=1; p:=[]; for u in [1..600000] do if not IsPrime(u) then p:=PrimeDivisors(u); s:=0; for i in [1..#p] do if IsIntegral((u-1)/(p[i]-1)) and IsIntegral((u+1)/(p[i]+1)) then s:=s+1; end if; if s eq #p then sol[m]:=u; m:=m+1; end if; end for; end if; end for; sol; // _Marius A. Burtea_, May 16 2019

%Y Cf. A056729, A056824, A080062.

%K nonn

%O 1,1

%A _Paolo P. Lava_, May 17 2018