A024556 -id:A024556 - cp's OEIS frontend

A307964 Irregular triangle read by rows: T(n,k) = A308121(A024556(n),k).

7, 14, 13, 4, 11, 2, 1, 8, 3, 6, 5, 8, 3, 2, 5, 4, -1, 2, 1, 4, 13, 26, 19, 32, 25, 38, 31, 4, 17, 10, 23, 16, 29, 2, -5, 8, 1, 14, 7, 20, 11, 22, 33, 44, 31, 18, 29, 16, 27, 38, 1, 12, 23, 34, -3, 8, 19, 6, 17, 4, -9, 2, 13, 24, 5, 10, 7, 12, 9, 14, 11, 16, 5

Offset: 1

Jamie Morken, Jul 29 2019

The sequence gives odd squarefree composite rows n in A308121, i.e., rows 15, 21, 33, 35, 39, 51, 55, 57, 65, ... given by A024556(n).  These rows are the primitive rows of A308121.
Row n has length A000010(A024556(n)).
For row n:
  T(n, 1) = T(n, 2) / 2.
  T(n, phi(n)) - T(n, phi(n)-1) = T(n, 1).
  T(n, phi(n)/2+1) - T(n, phi(n)/2) = T(n, 1).
From Charlie Neder, Jul 30 2019: (Start)
For row n, T(n, k) + T(n, phi(n)-k) is constant for all k.
For 2 <= k < lpf(A024556(n)), T(n, k) = k*T(n, 1). (End)

			The sequence as an irregular triangle:
1:  7, 14, 13, 4, 11, 2, 1, 8;
2:  3, 6, 5, 8, 3, 2, 5, 4, -1, 2, 1, 4;
3:  13, 26, 19, 32, 25, 38, 31, 4, 17, 10, 23, 16, 29, 2, -5, 8, 1, 14, 7, 20;
4:  11, 22, 33, 44, 31, 18, 29, 16, 27, 38, 1, 12, 23, 34, -3, 8, 19, 6, 17, 4, -9, 2, 13, 24;
5:  5, 10, 7, 12, 9, 14, 11, 16, 5, 2, 7, 4, 9, 6, 11, 8, -3, 2, -1, 4, 1, 6, 3, 8
6:  19, 38, 25, 44, 31, 50, 37, 56, 43, 62, 49, 4, 23, 10, 29, 16, 35, 22, 41, 28, 47, 2, -11, 8, -5, 14, 1, 20, 7, 26, 13, 32;
7:  3, 6, 9, 12, 7, 10, 13, 16, 3, 6, 9, 4, 7, 10, 13, 8, 3, 6, 1, 4, 7, 10, 5, 8, 3, -2, 1, 4, 7, 2, 5, 8, -5, -2, 1, 4, -1, 2, 5, 8;
8:  7, 14, 9, 16, 11, 18, 13, 20, 15, 22, 17, 24, 7, 2, 9, 4, 11, 6, 13, 8, 15, 10, 17, 12, -5, 2, -3, 4, -1, 6, 1, 8, 3, 10, 5, 12;
9:  17, 34, 51, 68, 37, 54, 71, 88, 57, 74, 43, 12, 29, 46, 63, 32, 49, 66, 83, 4, 21, 38, 7, 24, 41, 58, 27, 44, 61, -18, -1, 16, 33, 2, 19, 36, 53, 22, -9, 8, -23, -6, 11, 28, -3, 14, 31, 48;
  ...

Jamie Morken, Table of n, a(n) for n = 1..9768

Cf. A024556, A308121, A309497, A000010, A076511, A076512.

rowsToCheck = 340;
A024556 =
Complement[Select[Range[3, rowsToCheck, 2], SquareFreeQ],
  Prime[Range[
    PrimePi[rowsToCheck]]]]; (* after Harvey P. Dale , Jan 26 2011 *)
A308121 =
Table[With[{a = n/GCD[n, #], b = Numerator[#/n]},
     MapIndexed[a First@#2 - b #1 &,
      Flatten@Position[GCD[Table[Mod[k, n], {k, n - 1}], n],
         1] /. {} -> {1}]] &@EulerPhi@n, {n,
   rowsToCheck}]; (* after Michael De Vlieger, Jun 06 2019 *)
A307964 = {};
For[i = 1, i <= Length[A024556], i++,
AppendTo[A307964, A308121[[A024556[[i]]]]]]
A307964flattened = Flatten[A307964]
(* Jamie Morken, Apr 20 2021 *)

A002997 Carmichael numbers: composite numbers k such that a^(k-1) == 1 (mod k) for every a coprime to k.

Original entry on oeis.org

561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881, 512461, 530881, 552721

Offset: 1

N. J. A. Sloane

V. Šimerka found the first 7 terms of this sequence 25 years before Carmichael (see the link and also the remark of K. Conrad). - Peter Luschny, Apr 01 2019
k is composite and squarefree and for p prime, p|k => p-1|k-1.
An odd composite number k is a pseudoprime to base a iff a^(k-1) == 1 (mod k). A Carmichael number is an odd composite number k which is a pseudoprime to base a for every number a prime to k.
A composite odd number k is a Carmichael number if and only if k is squarefree and p-1 divides k-1 for every prime p dividing k. (Korselt, 1899)
Ghatage and Scott prove using Fermat's little theorem that (a+b)^k == a^k + b^k (mod k) (the freshman's dream) exactly when k is a prime (A000040) or a Carmichael number. - Jonathan Vos Post, Aug 31 2005
Alford et al. have constructed a Carmichael number with 10333229505 prime factors, and have also constructed Carmichael numbers with m prime factors for every m between 3 and 19565220. - Jonathan Vos Post, Apr 01 2012
Thomas Wright proved that for any numbers b and M in N with gcd(b,M) = 1, there are infinitely many Carmichael numbers k such that k == b (mod M). - Jonathan Vos Post, Dec 27 2012
Composite numbers k relatively prime to 1^(k-1) + 2^(k-1) + ... + (k-1)^(k-1). - Thomas Ordowski, Oct 09 2013
Composite numbers k such that A063994(k) = A000010(k). - Thomas Ordowski, Dec 17 2013
Odd composite numbers k such that k divides A002445((k-1)/2). - Robert Israel, Oct 02 2015
If k is a Carmichael number and gcd(b-1,k)=1, then (b^k-1)/(b-1) is a pseudoprime to base b by Steuerwald's theorem; see the reference in A005935. - Thomas Ordowski, Apr 17 2016
Composite numbers k such that p^k == p (mod k) for every prime p <= A285512(k). - Max Alekseyev and Thomas Ordowski, Apr 20 2017
If a composite m < A285549(n) and p^m == p (mod m) for every prime p <= prime(n), then m is a Carmichael number. - Thomas Ordowski, Apr 23 2017
The sequence of all Carmichael numbers can be defined as follows: a(1) = 561, a(n+1) = smallest composite k > a(n) such that p^k == p (mod k) for every prime p <= n+2. - Thomas Ordowski, Apr 24 2017
An integer m > 1 is a Carmichael number if and only if m is squarefree and each of its prime divisors p satisfies both s_p(m) >= p and s_p(m) == 1 (mod p-1), where s_p(m) is the sum of the base-p digits of m. Then m is odd and has at least three prime factors. For each prime factor p, the sharp bound p <= a*sqrt(m) holds with a = sqrt(17/33) = 0.7177.... See Kellner and Sondow 2019. - Bernd C. Kellner and Jonathan Sondow, Mar 03 2019
Carmichael numbers are special polygonal numbers A324973. The rank of the n-th Carmichael number is A324975(n). See Kellner and Sondow 2019. - Jonathan Sondow, Mar 26 2019
An odd composite number m is a Carmichael number iff m divides denominator(Bernoulli(m-1)). The quotient is A324977. See Pomerance, Selfridge, & Wagstaff, p. 1006, and Kellner & Sondow, section on Bernoulli numbers. - Jonathan Sondow, Mar 28 2019
This is setwise difference A324050 \ A008578. Many of the same identities apply also to A324050. - Antti Karttunen, Apr 22 2019
If k is a Carmichael number, then A309132(k) = A326690(k). The proof generalizes that of Theorem in A309132. - Jonathan Sondow, Jul 19 2019
Composite numbers k such that A111076(k)^(k-1) == 1 (mod k). Proof: the multiplicative order of A111076(k) mod k is equal to lambda(k), where lambda(k) = A002322(k), so lambda(k) divides k-1, qed. - Thomas Ordowski, Nov 14 2019
For all positive integers m, m^k - m is divisible by k, for all k > 1, iff k is either a Carmichael number or a prime, as is used in the proof by induction for Fermat's Little Theorem. Also related are A182816 and A121707. - Richard R. Forberg, Jul 18 2020
From Amiram Eldar, Dec 04 2020, Apr 21 2024: (Start)
Ore (1948) called these numbers "Numbers with the Fermat property", or, for short, "F numbers".
Also called "absolute pseudoprimes". According to Erdős (1949) this term was coined by D. H. Lehmer.
Named by Beeger (1950) after the American mathematician Robert Daniel Carmichael (1879 - 1967). (End)
For ending digit 1,3,5,7,9 through the first 10000 terms, we see 80.3, 4.1, 7.4, 3.8 and 4.3% apportionment respectively. Why the bias towards ending digit "1"? - Bill McEachen, Jul 16 2021
It seems that for any m > 1, the remainders of Carmichael numbers modulo m are biased towards 1. The number of terms congruent to 1 modulo 4, 6, 8, ..., 24 among the first 10000 terms: 9827, 9854, 8652, 8034, 9682, 5685, 6798, 7820, 7880, 3378 and 8518. - Jianing Song, Nov 08 2021
Alford, Granville and Pomerance conjectured in their 1994 paper that a statement analogous to Bertrand's Postulate could be applied to Carmichael numbers. This has now been proved by Daniel Larsen, see link below. - David James Sycamore, Jan 17 2023

N. G. W. H. Beeger, On composite numbers n for which a^n == 1 (mod n) for every a prime to n, Scripta Mathematica, Vol. 16 (1950), pp. 133-135.
Albert H. Beiler, Recreations in the Theory of Numbers, Dover Publications, Inc. New York, 1966, Table 18, Page 44.
David M. Burton, Elementary Number Theory, 5th ed., McGraw-Hill, 2002.
John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See p. 142.
CRC Standard Mathematical Tables and Formulae, 30th ed., 1996, p. 87.
Richard K. Guy, Unsolved Problems in Number Theory, A13.
Øystein Ore, Number Theory and Its History, McGraw-Hill, 1948, Reprinted by Dover Publications, 1988, Chapter 14.
Paul Poulet, Tables des nombres composés vérifiant le théorème du Fermat pour le module 2 jusqu'à 100.000.000, Sphinx (Brussels), 8 (1938), 42-45.
Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See pp. 22, 100-103.
Wacław Sierpiński, A Selection of Problems in the Theory of Numbers. Macmillan, NY, 1964, p. 51.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, pages 145-146.
David Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, Revised edition 1987. See entry 561 at p. 157.

N. J. A. Sloane, Table of n, a(n) for n = 1..10000 (from the Pinch web site mentioned below)
W. R. Alford, Jon Grantham, Steven Hayman, and Andrew Shallue, Constructing Carmichael numbers through improved subset-product algorithms, Mathematics of Computation, Vol. 83, No. 286 (2014), pp. 899-915, arXiv preprint, arXiv:1203.6664v1 [math.NT], Mar 29 2012.
W. R. Alford, A. Granville, and C. Pomerance, There are infinitely many Carmichael numbers, Ann. of Math. (2) 139 (1994), no. 3, 703-722.
W. R. Alford, A. Granville, and C. Pomerance (1994). "On the difficulty of finding reliable witnesses". Lecture Notes in Computer Science 877, 1994, pp. 1-16.
François Arnault, Thesis.
François Arnault, Constructing Carmichael numbers which are strong pseudoprimes to several bases, Journal of Symbolic Computation, vol. 20, no 2, Aug. 1995, pp. 151-161.
François Arnault, Rabin-Miller primality test: Composite numbers which pass it, Mathematics of Computation, vol. 64, no 209, 1995, pp. 355-361.
François Arnault, The Rabin-Monier theorem for Lucas pseudoprimes, Mathematics of Computation, vol. 66, no 218, April 1997, pp. 869-881.
Joerg Arndt, Matters Computational (The Fxtbook), p. 786.
Eric Bach and Rex Fernando, Infinitely Many Carmichael Numbers for a Modified Miller-Rabin Prime Test, ISSAC '16: Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, July 2016, pp. 47-54, arXiv preprint, arXiv:1512.00444 [math.NT], 2015.
Sunghan Bae, Su Hu, and Min Sha, On the Carmichael rings, Carmichael ideals and Carmichael polynomials, arXiv:1809.05432 [math.NT], 2018.
Jonathan Bayless and Paul Kinlaw, Explicit Bounds for the Sum of Reciprocals of Pseudoprimes and Carmichael Numbers, Journal of Integer Sequences, Vol. 20 (2017), Article 17.6.4.
Jens Bernheiden, Carmichael numbers (Text in German).
John D. Brillhart, N. J. A. Sloane, and J. D. Swift, Correspondence, 1972.
Ronald Joseph Burthe, Jr. Upper bounds for least witnesses and generating sets, Acta Arith. 80 (1997), no. 4, 311-326.
C. K. Caldwell, The Prime Glossary, Carmichael number.
R. D. Carmichael, Note on a new number theory function, Bull. Amer. Math. Soc. 16 (1910), 232-238.
Keith Conrad, Carmichael numbers and Korselt's criterion, expository paper (2016), 1-3.
K. A. Draziotis, V. Martidis, and S. Tiganourias, Product Subset Problem: Applications to number theory and cryptography, arXiv:2002.07095 [math.NT], 2020. See also Chapter 5, Analysis, Cryptography and Information Science, World Scientific (2023), p. 108.
Harvey Dubner, Carmichael Numbers of the form (6m+1)(12m+1)(18m+1), Journal of Integer Sequences, Vol. 5 (2002) Article 02.2.1.
James Emery, Number Theory, 2013. [Broken link]
Paul Erdős, On the converse of Fermat's theorem, The American Mathematical Monthly, Vol. 56, No. 9 (1949), pp. 623-624; alternative link.
Jan Feitsma and William Galway, Tables of pseudoprimes and related data.
Pratibha Ghatage and Brian Scott, Exactly When is (a+b)^n == a^n + b^n (mod n)?, College Mathematics Journal, Vol. 36, No. 4 (Sep 2005), p. 322.
Claude Goutier, Compressed text file carm10e22.7z containing all the Carmichael numbers up to 10^22. [Local copy, with permission. This is a very large file.]
Andrew Granville, Papers on Carmichael numbers.
Andrew Granville, Primality testing and Carmichael numbers, Notices Amer. Math. Soc., 39 (No. 7, 1992), 696-700.
Andrew Granville and Carl Pomerance, Two contradictory conjectures concerning Carmichael numbers, Math. Comp. 71 (2002), no. 238, 883-908.
Gerhard Jaeschke, The Carmichael numbers to 10^12, Math. Comp., Vol. 55, No. 191 (1990), pp. 383-389.
Eugene Karolinsky and Dmytro Seliutin, Carmichael numbers for GL(m), arXiv:2001.10315 [math.NT], 2020.
Bernd C. Kellner, On primary Carmichael numbers, Integers 22 (2022), #A38, 39 pp.; arXiv:1902.11283 [math.NT], 2019.
Bernd C. Kellner and Jonathan Sondow, On Carmichael and polygonal numbers, Bernoulli polynomials, and sums of base-p digits, Integers 21 (2021), #A52, 21 pp.; arXiv:1902.10672 [math.NT], 2019.
Paul Kinlaw, The reciprocal sums of pseudoprimes and Carmichael numbers, Mathematics of Computation (2023).
A. Korselt, G. Tarry, I. Franel, and G. Vacca, Problème chinois, L'intermédiaire des mathématiciens 6 (1899), 142-144.
Daniel Larsen, Bertrand's Postulate for Carmichael Numbers, arXiv:2111.06963 [math.NT], 2021.
D. H. Lehmer, Errata for Poulet's table, Math. Comp., 25 (1971), 944-945. 25 944 1971.
Max Lewis and Victor Scharaschkin, k-Lehmer and k-Carmichael Numbers, Integers, 16 (2016), #A80.
Renaud Lifchitz, A generalization of the Korselt's criterion - Nested Carmichael numbers.
Romeo Meštrović, Generalizations of Carmichael numbers I, arXiv:1305.1867v1 [math.NT], May 04 2013.
Romeo Meštrović, On a Congruence Modulo n^3 Involving Two Consecutive Sums of Powers, Journal of Integer Sequences, Vol. 17 (2014), 14.8.4.
Yoshio Mimura, Carmichael Numbers up to 10^12. [broken link, WayBackMachine]
Math Reference Project, Carmichael Numbers.
R. G. E. Pinch, The Carmichael numbers up to 10^18, 2008.
R. G. E. Pinch, Carmichael numbers up to 10^15, 10^16, 10^16 to 10^17, 10^17 to 10^18, 10^19, and 10^21.
Carl Pomerance, J. L. Selfridge, and Samuel S. Wagstaff, Jr., The pseudoprimes to 25*10^9, Math. Comp., Vol. 35, No. 151 (1980), pp. 1003-1026.
Carl Pomerance and N. J. A. Sloane, Correspondence, 1991.
Fred Richman, Primality testing with Fermat's little theorem.
Vladimir Shevelev, The number of permutations with prescribed up-down structure as a function of two variables, INTEGERS, 12 (2012), #A1. - From _N. J. A. Sloane_, Feb 07 2013
Václav Šimerka, Zbytky z arithmetické posloupnosti, (On the remainders of an arithmetic progression), Časopis pro pěstování matematiky a fysiky. 14 (1885), 221-225.
Eric Weisstein's World of Mathematics, Carmichael Number, Knoedel Numbers, and Pseudoprime.
Wikipedia, Carmichael number.
Thomas Wright, Infinitely many Carmichael numbers in arithmetic progressions, Bulletin of the London Mathematical Society, 45 (2013) 943-952, arXiv preprint, arXiv:1212.5850 [math.NT], Dec 2012.
Index entries for sequences related to Carmichael numbers.

Cf. A001567, A002445, A002322, A006931, A024556, A027748, A055553, A064238-A064262, A083737, A087441, A087442, A135717, A141711, A153581, A225498, A285512, A285549, A309132, A324290, A324315, A324316, A324973, A324975, A324977, A326690.

Subsequence of A324050.

a002997 n = a002997_list !! (n-1)
a002997_list = [x | x <- a024556_list,
all (== 0) $ map ((mod (x - 1)) . (subtract 1)) $ a027748_row x]
-- Reinhard Zumkeller, Apr 12 2012

[n: n in [3..53*10^4 by 2] | not IsPrime(n) and n mod CarmichaelLambda(n) eq 1]; // Bruno Berselli, Apr 23 2012

filter:= proc(n)
  local q;
  if isprime(n) then return false fi;
  if 2 &^ (n-1) mod n <> 1 then return false fi;
  if not numtheory:-issqrfree(n) then return false fi;
  for q in numtheory:-factorset(n) do
    if (n-1) mod (q-1) <> 0 then return false fi
  od:
  true;
end proc:
select(filter, [seq(2*k+1,k=1..10^6)]); # Robert Israel, Dec 29 2014
isA002997 := n -> 0 = modp(n-1, numtheory:-lambda(n)) and not isprime(n) and n <> 1:
select(isA002997, [$1..10000]); # Peter Luschny, Jul 21 2019

Cases[Range[1,100000,2], n_ /; Mod[n, CarmichaelLambda[n]] == 1 && ! PrimeQ[n]] (* Artur Jasinski, Apr 05 2008; minor edit from Zak Seidov, Feb 16 2011 *)
Select[Range[1,600001,2],CompositeQ[#]&&Mod[#,CarmichaelLambda[#]]==1&] (* Harvey P. Dale, Jul 08 2023 *)

Korselt(n)=my(f=factor(n));for(i=1,#f[,1],if(f[i,2]>1||(n-1)%(f[i,1]-1),return(0)));1
isA002997(n)=n%2 && !isprime(n) && Korselt(n) && n>1 \\ Charles R Greathouse IV, Jun 10 2011

is_A002997(n, F=factor(n)~)={ #F>2 && !foreach(F,f,(n%(f[1]-1)==1 && f[2]==1) || return)} \\ No need to check parity: if efficiency is needed, scan only odd numbers. - M. F. Hasler, Aug 24 2012, edited Mar 24 2022

from itertools import islice
from sympy import nextprime, factorint
def A002997_gen(): # generator of terms
    p, q = 3, 5
    while True:
        for n in range(p+2,q,2):
            f = factorint(n)
            if max(f.values()) == 1 and not any((n-1) % (p-1) for p in f):
                yield n
        p, q = q, nextprime(q)
A002997_list = list(islice(A002997_gen(),20)) # Chai Wah Wu, May 11 2022

def isCarmichael(n):
    if n == 1 or is_even(n) or is_prime(n):
        return False
    factors = factor(n)
    for f in factors:
        if f[1] > 1: return False
        if (n - 1) % (f[0] - 1) != 0:
            return False
    return True
print([n for n in (1..20000) if isCarmichael(n)]) # Peter Luschny, Apr 02 2019

Sum_{n>=1} 1/a(n) is in the interval (0.004706, 27.8724) (Bayless and Kinlaw, 2017). The upper bound was reduced to 0.0058 by Kinlaw (2023). - Amiram Eldar, Oct 26 2020, Feb 24 2024

Links for lists of Carmichael numbers updated by Jan Kristian Haugland, Mar 25 2009 and Danny Rorabaugh, May 05 2017

A046388 Odd numbers of the form p*q where p and q are distinct primes.

Original entry on oeis.org

15, 21, 33, 35, 39, 51, 55, 57, 65, 69, 77, 85, 87, 91, 93, 95, 111, 115, 119, 123, 129, 133, 141, 143, 145, 155, 159, 161, 177, 183, 185, 187, 201, 203, 205, 209, 213, 215, 217, 219, 221, 235, 237, 247, 249, 253, 259, 265, 267, 287, 291, 295, 299, 301, 303

Offset: 1

Patrick De Geest, Jun 15 1998

nonn

These are the odd squarefree semiprimes.

These numbers k have the property that k is a Fermat pseudoprime for at least two bases 1 < b < k - 1. That is, b^(k - 1) == 1 (mod k). See sequence A175101 for the number of bases. - Karsten Meyer, Dec 02 2010

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)

Intersection of A005117 and A046315, or equally, of A005408 and A006881, or of A001358 and A056911.
Union of A080774 and A190299, which the latter is the union of A131574 and A016105.
Subsequence of A024556 and of A225375.
Cf. A353481 (characteristic function).
Cf. A001221, A046404, A056911, A175101.
Different from A056913, A098905, A225375.

a046388 n = a046388_list !! (n-1)
a046388_list = filter ((== 2) . a001221) a056911_list
-- Reinhard Zumkeller, Jan 02 2014

max = 300; A046388 = Sort@Flatten@Table[Prime[m] Prime[n], {n, 3, Ceiling[PrimePi[max/3]]}, {m, 2, n - 1}]; Select[A046388, # < max &] (* Alonso del Arte based on Robert G. Wilson v's program for A006881, Oct 24 2011 *)

isok(n) = (n % 2) && (bigomega(n) == 2) && (omega(n)==2); \\ Michel Marcus, Feb 05 2015

from sympy import factorint
def ok(n):
    if n < 2 or n%2 == 0: return False
    f = factorint(n)
    return len(f) == 2 and sum(f.values()) == 2
print([k for k in range(304) if ok(k)]) # Michael S. Branicky, May 03 2022

from math import isqrt
from sympy import primepi, primerange
def A046388(n):
    if n == 1: return 15
    def f(x): return int(n-1+x+(t:=primepi(s:=isqrt(x)))+(t*(t-1)>>1)-sum(primepi(x//k) for k in primerange(3, s+1)))
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    return bisection(f,n,n) # Chai Wah Wu, Sep 10 2024

Sum_{n>=1} 1/a(n)^s = (1/2)*(P(s)^2 - P(2*s)) + 1/4^s - P(s)/2^s, for s>1, where P is the prime zeta function. - Amiram Eldar, Nov 21 2020

I removed some ambiguity in the definition and edited the entry, merging in some material from A146166. - N. J. A. Sloane, May 09 2013

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

Original entry on oeis.org

399, 935, 2015, 2915, 4991, 5719, 7055, 8855, 12719, 18095, 20705, 20999, 22847, 29315, 31535, 46079, 51359, 60059, 63503, 67199, 73535, 76751, 80189, 81719, 88559, 90287, 104663, 117215, 120581, 147455, 152279, 155819, 162687, 191807, 194327, 196559, 214199

Offset: 1

Richard Pinch and Jeffrey Shallit

nonn

Wright proves that this sequence is infinite (Main Theorem 2). - Charles R Greathouse IV, Nov 03 2015
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
A composite k is a Lucas-Carmichael number if and only if k | A322702(k+1). - Thomas Ordowski, May 06 2021

J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 399, p. 89, Ellipses, Paris 2008.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Donovan Johnson, Table of n, a(n) for n = 1..10000 (first 550 terms from Paolo P. Lava)
Ed Copeland and Brady Haran, Something special about 399, Numberphile video (2015).
Sridhar Tamilvanan and Subramani Muthukrishnan, On Lucas-Carmichael Integer, arXiv:2311.08012 [math.NT], 2023.
Daniel Suteu, Table of n, a(n) for terms a(n) < 10^15.
Samuel S. Wagstaff, Jr., Ramanujan's Taxicab Number and its Ilk, Purdue Univ. (2024). See p. 2.
Wikipedia, Lucas-Carmichael number
Thomas Wright, There are infinitely many elliptic Carmichael numbers
Thomas Wright, There are infinitely many elliptic Carmichael numbers, arXiv:1609.00231 [math.NT], 2016.
Index entries for sequences related to Carmichael numbers.

Intersection of A024556 and A056729.
Cf. A216925, A216926, A216927, A217002, A217003, A217091 (terms having 3, 4, 5, 6, 7 and 8 factors).
Cf. A216929, A322702.

with(numtheory):
a:= proc(n) option remember; local k; for k from 1+
     `if`(n=1, 3, a(n-1)) while isprime(k) or not issqrfree(k)
       or add(irem(k+1,i+1), i=factorset(k))>0 do od; k
    end:
seq(a(n), n=1..15);  # Alois P. Heinz, Apr 05 2018

Select[ Range[ 2, 10^6 ], !PrimeQ[ # ] && Union[ Transpose[ FactorInteger[ # ] ][ [ 2 ] ] ] == {1} && Union[ Mod[ # + 1, Transpose[ FactorInteger[ # ] ][ [ 1 ] ] + 1 ] ] == {0} & ]

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

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);
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

A050384 Nonprimes such that n and phi(n) are relatively prime.

Original entry on oeis.org

1, 15, 33, 35, 51, 65, 69, 77, 85, 87, 91, 95, 115, 119, 123, 133, 141, 143, 145, 159, 161, 177, 185, 187, 209, 213, 215, 217, 221, 235, 247, 249, 255, 259, 265, 267, 287, 295, 299, 303, 319, 321, 323, 329, 335, 339, 341, 345, 365, 371, 377, 391, 393, 395, 403

Offset: 1

Christian G. Bower, Nov 15 1999

nonn

Also nonprimes n such that there is only one group of order n, i.e., A000001(n) = 1.
Intersection of A018252 and A003277.
Also numbers n such that n and A051953(n) are relatively prime. - Labos Elemer
Apart from the first term, this is a subsequence of A024556. - Charles R Greathouse IV, Apr 15 2015
Every Carmichael number and each of its nonprime divisors is in this sequence. - Emmanuel Vantieghem, Apr 20 2015
An alternative definition (excluding the 1): k is strongly prime to n <=> k is prime to n and k does not divide n - 1 (cf. A181830). n is cyclic if n is prime to phi(n). n is strongly cyclic if phi(n) is strongly prime to n. The a(n) are the strongly cyclic numbers apart from a(1). - Peter Luschny, Nov 14 2018

T. D. Noe, Table of n, a(n) for n = 1..10000
Joel E. Cohen, Conjectures about Primes and Cyclic Numbers, arXiv:2508.08335 [math.NT], 2025. See pp. 2, 6.
Peter Luschny, Strong coprimality, 2011.

If the primes are included we get A003277. Cf. A000001, A000010 (phi), A181830, A181837.

isStrongPrimeTo := (n, k) -> (igcd(n, k) = 1) and not (irem(n-1, k) = 0):
isStrongCyclic := n -> isStrongPrimeTo(n, numtheory:-phi(n)):
[1, op(select(isStrongCyclic, [$(2..404)]))]; # Peter Luschny, Dec 13 2021

Select[Range[450], !PrimeQ[#] && GCD[#, EulerPhi[#]] == 1&] (* Harvey P. Dale, Jan 31 2011 *)

is(n)=!isprime(n) && gcd(eulerphi(n),n)==1 \\ Charles R Greathouse IV, Apr 15 2015

def isStrongPrimeTo(n, m): return gcd(n, m) == 1 and not m.divides(n-1)
def isStrongCyclic(n): return isStrongPrimeTo(n, euler_phi(n))
[1] + [n for n in (1..403) if isStrongCyclic(n)] # Peter Luschny, Nov 14 2018

A053850 Odd numbers divisible by a square > 1.

Original entry on oeis.org

9, 25, 27, 45, 49, 63, 75, 81, 99, 117, 121, 125, 135, 147, 153, 169, 171, 175, 189, 207, 225, 243, 245, 261, 275, 279, 289, 297, 315, 325, 333, 343, 351, 361, 363, 369, 375, 387, 405, 423, 425, 441, 459, 475, 477, 495, 507, 513, 525, 529, 531, 539, 549, 567

Offset: 1

Enoch Haga, Mar 28 2000

Odd n such that sum(k=1,n-1,floor(k^3/n)) is different from (1/4)*(n-2)*(n^2-1) (equality holds for n prime as well as for "1" union "A024556" ). - Benoit Cloitre, Dec 08 2002
Odd nonsquarefree numbers, odd terms of A013929. - Zak Seidov, Aug 16 2006
The asymptotic density of this sequence is 1/2 - 4/Pi^2 = 0.094715... - Amiram Eldar, Nov 21 2020

Amiram Eldar, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Prime Sums.

Cf. A078837, A013929, A024556.

Select[Range[1, 500, 2], !SquareFreeQ[#] &] (* Amiram Eldar, Nov 21 2020 *)

lista(nn) = {forstep(n=1, nn, 2, if (! issquarefree(n), print1(n, ", ")));} \\ Michel Marcus, Jun 06 2014

A238711 Product of all primes p such that 2n - p is also prime.

Original entry on oeis.org

2, 3, 15, 105, 35, 231, 2145, 5005, 4641, 53295, 1616615, 119301, 21505, 7436429, 21489, 57998985, 3038795305, 4123, 13844919, 10393190665, 12838371, 299859855, 7292509103495, 12023917269, 70691995, 37198413949697, 62483343, 2769282065, 98755025688454681

Offset: 2

Reinhard Zumkeller, Mar 06 2014

nonn

Product of n-th row in triangle A171637;
All terms greater than 3 are odd, composite and squarefree numbers, cf. A024556.
n is prime iff n is a factor of a(n).
Product of the distinct primes in the Goldbach partitions of 2n. - Wesley Ivan Hurt, Sep 29 2020

Reinhard Zumkeller, Table of n, a(n) for n = 2..2000

Cf. A000040, A010051, A238778, subsequence of A056911.

a238711 n = product $ filter ((== 1) . a010051') $
   map (2 * n -) $ takeWhile (<= 2 * n) a000040_list

Table[Times@@Select[Select[Prime[Range[2 n]], # < 2 n &], PrimeQ[2 n - #] &], {n, 2, 30}] (* Robert Price, Apr 26 2025 *)

A020639(a(n)) = A020481(n); A006530(a(n)) = A020482(n);
A001221(a(n)) = A035026(n); A008472(a(n)) = A238778(n);
A027748(a(n),k) + A027748(a(n),l+1-k) = 2*n for k=1..l, with l=A001221(a(n)); particulary A020639(a(n))+A006530(a(n)) = 2*n;
a(n) = n^c(n) * Product_{i=1..n-1} (i*(2*n-i))^(c(i)*c(2*n-i)), where c is the prime characteristic (A010051). - Wesley Ivan Hurt, Sep 29 2020

A225375 Odd numbers with exactly 2 distinct prime factors.

Original entry on oeis.org

15, 21, 33, 35, 39, 45, 51, 55, 57, 63, 65, 69, 75, 77, 85, 87, 91, 93, 95, 99, 111, 115, 117, 119, 123, 129, 133, 135, 141, 143, 145, 147, 153, 155, 159, 161, 171, 175, 177, 183, 185, 187, 189, 201, 203, 205, 207, 209, 213, 215, 217, 219, 221, 225, 235, 237

Offset: 1

R. J. Mathar, Oct 13 2008

nonn

Numbers of the form p^i*q^j where p, q are distinct odd primes and i>=1, j>=1.

Subset of A098905 (which contains in addition A046390 and numbers like 255255, 285285, 345345, 373065 etc.).

Subsequence of A272592. A046388 is a subsequence.
Cf. A046315, A046390, A046404, A024556, A056913.
Different from A046388, A098905.

isA225375 := proc(n) RETURN( (n mod 2 = 1) and (A001221(n) = 2) ); end proc:
for n from 1 to 840 do if isA225375(n) then printf("%d,",n) ; end if; end do:

Select[2 Range[200] + 1, PrimeNu[#] == 2&] (* Jean-François Alcover, Apr 04 2020 *)

is_A046388(n)={ bittest(n,0) & omega(n)==2 } \\ M. F. Hasler, Feb 13 2012

Entry created by N. J. A. Sloane, May 09 2013 in order to restore the original definition of A046388.

A231370 Squarefree composite numbers k such that 2 is a primitive root for all prime factors of k.

Original entry on oeis.org

15, 33, 39, 55, 57, 65, 87, 95, 111, 143, 145, 159, 165, 177, 183, 185, 195, 201, 209, 247, 249, 265, 285, 295, 303, 305, 319, 321, 335, 377, 393, 407, 415, 417, 429, 435, 447, 481, 489, 505, 519, 535, 537, 543, 551, 555, 583, 591, 627, 633, 649, 655, 671, 681

Offset: 1

Arkadiusz Wesolowski, Nov 08 2013

nonn

If k is the smallest integer satisfying 10^k == 1 (mod p), we say that 10 has order k (mod p). If n is the product of distinct primes p_i, the period of 1/n in base b is the least common multiple of the orders of b (mod p_i), provided b and n are relatively prime.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Primitive Root.
Wikipedia, Binary number.

Subsequence of A024556.

Cf. A001122, A231371, A231372.

q[n_] := CompositeQ[n] && SquareFreeQ[n] && AllTrue[FactorInteger[n][[;;,1]],  MultiplicativeOrder[2, #] == # - 1 &]; Select[Range[700], q] (* Amiram Eldar, Oct 03 2021 *)

isok(k) = if ((k>1) && (k%2) && !isprime(k) && issquarefree(k), my(f=factor(k)[,1]~); for (j=1, #f, if (znorder(Mod(2, f[j])) != (f[j]-1), return(0))); return (1)); return (0); \\ Michel Marcus, Oct 03 2021

A231371 Squarefree composite numbers k such that 8 is a primitive root for all prime factors of k.

Original entry on oeis.org

15, 33, 55, 87, 145, 159, 165, 177, 249, 265, 295, 303, 319, 321, 393, 415, 435, 447, 505, 519, 535, 537, 583, 591, 649, 655, 681, 745, 795, 807, 865, 879, 885, 895, 913, 951, 957, 985, 1041, 1111, 1135, 1167, 1177, 1245, 1257, 1329, 1345, 1383, 1401, 1441

Offset: 1

Arkadiusz Wesolowski, Nov 08 2013

nonn

Amiram Eldar, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Primitive Root.
Wikipedia, Octal.

Subsequence of A024556.

Cf. A019338, A231370, A231372.

q[n_] := CompositeQ[n] && SquareFreeQ[n] && AllTrue[FactorInteger[n][[;;,1]],  MultiplicativeOrder[8, #] == # - 1 &]; Select[Range[1441], q] (* Amiram Eldar, Oct 03 2021 *)

cp's OEIS Frontend

A307964 Irregular triangle read by rows: T(n,k) = A308121(A024556(n),k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A002997 Carmichael numbers: composite numbers k such that a^(k-1) == 1 (mod k) for every a coprime to k.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Sage

Formula

Extensions

A046388 Odd numbers of the form p*q where p and q are distinct primes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Python

Formula

Extensions

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

A050384 Nonprimes such that n and phi(n) are relatively prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

A053850 Odd numbers divisible by a square > 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI