login
a(n) is the smallest m with gcd(m, 2*n+1) = 1 such that 2*n + 2*m + 1 is composite.
4

%I #47 May 23 2021 02:55:24

%S 4,11,2,1,8,2,1,17,2,1,2,1,1,4,2,1,1,2,1,5,2,1,2,1,1,2,1,1,4,2,1,1,2,

%T 1,4,2,1,1,2,1,2,1,1,2,1,1,1,2,1,8,2,1,8,2,1,2,1,1,1,1,1,1,2,1,2,1,1,

%U 4,2,1,1,1,1,4,2,1,1,2,1,1,2,1,2,1,1,2,1

%N a(n) is the smallest m with gcd(m, 2*n+1) = 1 such that 2*n + 2*m + 1 is composite.

%C Starting at 2*n + 1, find the next odd composite number 2*n + 2*m + 1 that is relatively prime to 2*n + 1; then a(n) = m.

%C Since 2*n + 3 is relatively prime to 2*n + 1, and (2*n + 3)^2 is composite, a(n) <= 2*n^2 + 5*n + 4 (this is tight for n=0 and n=1).

%C From _Andrey Zabolotskiy_, Feb 13 2017: (Start)

%C Up to n = 10^7, a(n) are from the set [1, 2, 4, 5, 7, 8, 11, 13, 14, 16, 17, 19, 22]. First occurrence of 14 is a(99412), first occurrence of 22 is a(7225627). [Thanks to _Altug Alkan_ for pointing out a(99412).]

%C a(n) = 1 iff n is in A153238.

%C (End)

%C Based on _Altug Alkan_'s b-file, the records in this sequence are 4, 11, 17, 19, ... and occur at positions 1, 2, 8, 638, ... If the sequence is unbounded, then these two subsidiary sequences should be added to the OEIS (if they are new). - _N. J. A. Sloane_, Feb 13 2017

%H Altug Alkan, <a href="/A282026/b282026.txt">Table of n, a(n) for n = 0..10000</a>

%e When n=1, 2*n + 1 = 3, and 5, 7, 9, 11, 13, 15, 17, 19, 21, 23 are all either prime or have a common factor with 3. The next term, 25, is OK, and so a(1) = (25 - 3)/2 = 11.

%t Table[m = 1; While[Nand[CoprimeQ[m, 2 n + 1], CompositeQ[2 (n + m) + 1]], m++]; m, {n, 0, 120}] (* _Michael De Vlieger_, Feb 18 2017 *)

%o (PARI) a(n) = my(k=1); while(isprime(2*n+2*k+1) || gcd(2*n+1, k) != 1, k++); k; \\ _Altug Alkan_, Feb 13 2017

%Y Cf. A153238, A282423, A282429.

%K nonn

%O 0,1

%A _N. J. A. Sloane_, Feb 12 2017

%E Definition corrected by _Altug Alkan_, Feb 13 2017