cp's OEIS Frontend

A006972 Lucas-Carmichael numbers: squarefree composite numbers k such that p | k => p+1 | k+1.

%I A006972 M5450 #113 Mar 29 2024 11:43:46
%S A006972 399,935,2015,2915,4991,5719,7055,8855,12719,18095,20705,20999,22847,
%T A006972 29315,31535,46079,51359,60059,63503,67199,73535,76751,80189,81719,
%U A006972 88559,90287,104663,117215,120581,147455,152279,155819,162687,191807,194327,196559,214199
%N A006972 Lucas-Carmichael numbers: squarefree composite numbers k such that p | k => p+1 | k+1.
%C A006972 Wright proves that this sequence is infinite (Main Theorem 2). - _Charles R Greathouse IV_, Nov 03 2015
%C A006972 Conjecture: if k = p*q*r, p = a*d - 1, q = b*d - 1, r = c*d - 1 are distinct odd primes, with d = gcd(p + 1, q + 1, r + 1) and a*b*c*d divides k + 1, then k is a Lucas-Carmichael number. - _Davide Rotondo_, Dec 23 2020
%C A006972 A composite k is a Lucas-Carmichael number if and only if k | A322702(k+1). - _Thomas Ordowski_, May 06 2021
%D A006972 J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 399, p. 89, Ellipses, Paris 2008.
%D A006972 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A006972 Donovan Johnson, <a href="/A006972/b006972.txt">Table of n, a(n) for n = 1..10000</a> (first 550 terms from Paolo P. Lava)
%H A006972 Ed Copeland and Brady Haran, <a href="https://www.youtube.com/watch?v=yfr3BIk6KFc">Something special about 399</a>, Numberphile video (2015).
%H A006972 Sridhar Tamilvanan and Subramani Muthukrishnan, <a href="https://arxiv.org/abs/2311.08012">On Lucas-Carmichael Integer</a>, arXiv:2311.08012 [math.NT], 2023.
%H A006972 Daniel Suteu, <a href="/A006972/a006972.txt">Table of n, a(n) for terms a(n) < 10^15</a>.
%H A006972 Samuel S. Wagstaff, Jr., <a href="https://homes.cerias.purdue.edu/~ssw/taxi.pdf">Ramanujan's Taxicab Number and its Ilk</a>, Purdue Univ. (2024). See p. 2.
%H A006972 Wikipedia, <a href="https://en.wikipedia.org/wiki/Lucas-Carmichael_number">Lucas-Carmichael number</a>
%H A006972 Thomas Wright, <a href="http://webs.wofford.edu/wrighttj/job/carmichael_elliptic_2.pdf">There are infinitely many elliptic Carmichael numbers</a>
%H A006972 Thomas Wright, <a href="https://arxiv.org/abs/1609.00231">There are infinitely many elliptic Carmichael numbers</a>, arXiv:1609.00231 [math.NT], 2016.
%H A006972 <a href="/index/Ca#Carmichael">Index entries for sequences related to Carmichael numbers</a>.
%p A006972 with(numtheory):
%p A006972 a:= proc(n) option remember; local k; for k from 1+
%p A006972      `if`(n=1, 3, a(n-1)) while isprime(k) or not issqrfree(k)
%p A006972        or add(irem(k+1,i+1), i=factorset(k))>0 do od; k
%p A006972     end:
%p A006972 seq(a(n), n=1..15);  # _Alois P. Heinz_, Apr 05 2018
%t A006972 Select[ Range[ 2, 10^6 ], !PrimeQ[ # ] && Union[ Transpose[ FactorInteger[ # ] ][ [ 2 ] ] ] == {1} && Union[ Mod[ # + 1, Transpose[ FactorInteger[ # ] ][ [ 1 ] ] + 1 ] ] == {0} & ]
%o A006972 (PARI) is(n)=my(f=factor(n));for(i=1,#f[,1],if((n+1)%(f[i,1]+1) || f[i,2]>1, return(0)));#f[,1]>1 \\ _Charles R Greathouse IV_, Sep 23 2012
%o A006972 (PARI)
%o A006972 lucas_carmichael(A, B, k) = A=max(A, vecprod(primes(k+1))\2); (f(m, l, lo, k) = my(list=List()); my(hi=min(sqrtint(B+1)-1, sqrtnint(B\m, k))); if(lo > hi, return(list)); if(k==1, lo=max(lo, ceil(A/m)); my(t=lift(-1/Mod(m,l))); while(t < lo, t += l); forstep(p=t, hi, l, if(isprime(p), my(n=m*p); if((n+1)%(p+1) == 0, listput(list, n)))), forprime(p=lo, hi, if(gcd(m, p+1) == 1, list=concat(list, f(m*p, lcm(l, p+1), p+1, k-1))))); list); f(1, 1, 3, k);
%o A006972 upto(n) = my(list=List()); for(k=3, oo, if(vecprod(primes(k+1))\2 > n, break); list=concat(list, lucas_carmichael(1, n, k))); vecsort(Vec(list)); \\ _Daniel Suteu_, Dec 01 2023
%Y A006972 Intersection of A024556 and A056729.
%Y A006972 Cf. A216925, A216926, A216927, A217002, A217003, A217091 (terms having 3, 4, 5, 6, 7 and 8 factors).
%Y A006972 Cf. A216929, A322702.
%K A006972 nonn
%O A006972 1,1
%A A006972 _Richard Pinch_ and _Jeffrey Shallit_