login
Composite numbers k such that k+d+1 is prime for all divisors d of k greater than 1.
4

%I #20 Mar 14 2023 14:38:28

%S 8,9,35,39,65,119,125,219,341,515,749,755,905,935,989,1043,1119,1343,

%T 1355,1469,1649,1829,1859,2519,3005,3161,3563,3953,4193,4269,4359,

%U 4613,4685,4769,4859,5123,5165,5249,5585,5699,5723,6005,6059,6239,6629,6879

%N Composite numbers k such that k+d+1 is prime for all divisors d of k greater than 1.

%C The sequence could begin with 1 by convention. The sequence in which d can be 1 is a subsequence. The elements are assumed composite so as to exclude the Sophie Germain primes (A005384) and (A045536). All terms except 8 and 9 are odd numbers in squarefree semiprimes (A006881) or 3-almost-primes (A014612). The only square is 9, the first few cubes are 8, 125, 357911=71^3, 6967871=191^3 and the first few 3-almost primes are 935=5*11*17, 1859=11*13^2, 11123=7^2*227, 305015=5*53*1151. The first 3-almost-prime divisible by 9 is 149049=3^2*16561. All elements not divisible by 3 are 5 or 11 mod 12. I have been unable to find an element with more than 3 prime factors. If one exists, it must be very large. One reason is that the number of divisors grows rapidly with the number of factors. For example, if n is squarefree with k factors, then tau(n)=2^k. The condition that the 2^k-1 numbers n+d+1 be prime is then quite strong. Another reason is that one or more of the numbers n+d+1 may always be composite. For example, if n=p^5, p prime, then both p^5+p^4+1 and p^5+p+1 are composite.

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

%e a(9)=935=5*11*17 since the divisors d greater than one are {5,11,17,55,85,187,935} and all elements in the set of n+d+1, {941,947,953,991,1021,1123,1871}, are primes.

%p with(numtheory); P:=[]: for w to 1 do for k from 2 do #start at 1, get first element 1 if not isprime(k) and isprime(2*k+1) then S:=divisors(k) minus {1,k}; Q:=map(z-> z+k+1, S); if andmap(isprime,Q) then P:=[op(P),k]; print(nops(P),k,ifactor(k)) fi; fd:=fopen("C:/temp/n+d+1=prime-1st-1000.txt",APPEND); fprintf(fd,"%d ",x); fclose(fd); if nops(P)=1000 then break fi; fi; od od;

%t Select[Range[7000],CompositeQ[#]&&AllTrue[#+1+Rest[Divisors[#]],PrimeQ]&] (* _Harvey P. Dale_, Mar 14 2023 *)

%o (PARI) is(n)=if(isprime(n)||n<8, return(0)); fordiv(n, d, if(!isprime(n+d+1), return(0))); 1 \\ _Charles R Greathouse IV_, Feb 05 2017

%Y Cf. A005384, A045536, A006881, A014612.

%K nonn

%O 1,1

%A _Walter Kehowski_, Jul 05 2006