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

8, 9, 35, 39, 65, 119, 125, 219, 341, 515, 749, 755, 905, 935, 989, 1043, 1119, 1343, 1355, 1469, 1649, 1829, 1859, 2519, 3005, 3161, 3563, 3953, 4193, 4269, 4359, 4613, 4685, 4769, 4859, 5123, 5165, 5249, 5585, 5699, 5723, 6005, 6059, 6239, 6629, 6879

Offset: 1

Author

Walter Kehowski, Jul 05 2006

Keywords

• nonn

Comments

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.

Examples

			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.
		

Links

• T. D. Noe, Table of n, a(n) for n = 1..1000

Crossrefs

Cf. A005384, A045536, A006881, A014612.

Programs

Maple

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;

Mathematica

Select[Range[7000],CompositeQ[#]&&AllTrue[#+1+Rest[Divisors[#]],PrimeQ]&] (* Harvey P. Dale, Mar 14 2023 *)

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