A120806 - OEIS

%I #22 Aug 05 2024 05:19:25

%S 1,3,5,9,11,29,35,39,41,65,125,179,191,239,281,419,431,641,659,749,

%T 755,809,905,935,989,1019,1031,1049,1229,1289,1451,1469,1481,1829,

%U 1859,1931,2129,2141,2339,2519,2549,2969,3161,3299,3329,3359,3389,3539,3821,3851

%N Positive integers k such that k+d+1 is prime for all divisors d of k.

%C No a(n) can be even, since a(n)+2 must be prime. If a(n) is a prime, then it is a Sophie Germain twin prime (A045536). The only square is 9. Let the degree of n be the sum of the exponents in its prime factorization. By convention, degree(1)=0. Then every a(n) has degree less than or equal to 3. Let the weight of n be the number of its distinct prime factors. By convention, weight(1)=0. Clearly, w<=d is always true, with d=w only when the number is squarefree. Let [w,d] be the set of all integers with weight w and degree d. Then only the following possibilities occur: 1. [0,0] => a(1)=1. 2. [1,1] => Sophie Germain twin prime: 3, 5, 11, 29, A005384, A045536. 3. [1,2] => a(4)=9 is the only occurrence. 4. [1,3] => 5^3, 71^3 and 303839^3 are the first few cubes, A000578, A120808. 5. [2,2] => 5*7, 3*13 and 5*13 are the first few semiprimes, A001358, A120807. 6. [2,3] => 11*13^2, 61^2*89 and 13^2*12671 are the first few examples, A014612, A054753, A120809. 7. [3,3] => 5*11*17, 5*53*1151, 5*11*42533 are the first few 3-almost primes, A007304, A120810.

%H T. D. Noe, <a href="/A120806/b120806.txt">Table of n, a(n) for n=1..1000</a>

%e a(11) = 125 since divisors(125) = {1, 5, 25, 125} and the set of all n+d+1 is {127, 131, 151, 251} and these are all primes.

%p with(numtheory); L:=[1]: for w to 1 do for k from 1 to 12^6 while nops(L)<=1000 do x:=2*k+1; if andmap(isprime,[x+2,2*x+1]) then S:=divisors(x) minus {1,x}; Q:=map(z-> x+z+1, S); if andmap(isprime,Q) then L:=[op(L),x]; print(nops(L),ifactor(x)); fi; fi; od od; L;

%t q[k_] := AllTrue[Divisors[k], PrimeQ[k + # + 1] &]; Select[Range[5000], q] (* _Amiram Eldar_, Aug 05 2024 *)

%o (PARI) is(n)=fordiv(n,d,if(!isprime(n+d+1),return(0)));1; \\ _Joerg Arndt_, Nov 07 2015

%Y Cf. A000578, A001358, A005384, A007304, A014612, A054753, A120776, A120807, A120808, A120809, A120810.

%K nonn

%O 1,2

%A _Walter Kehowski_, Jul 06 2006