cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-7 of 7 results.

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

Views

Author

N. J. A. Sloane

Keywords

Comments

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

References

  • 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.

Links

Crossrefs

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.

Programs

  • Haskell
    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
  • Magma
    [n: n in [3..53*10^4 by 2] | not IsPrime(n) and n mod CarmichaelLambda(n) eq 1]; // Bruno Berselli, Apr 23 2012
  • Maple
    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
  • Mathematica
    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 *)
  • PARI
    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
  • PARI
    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
  • Python
    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
  • Sage
    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

Formula

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

Extensions

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

A083876 Least pseudoprime to base 2 through base prime(n).

Original entry on oeis.org

341, 1105, 1729, 29341, 29341, 162401, 252601, 252601, 252601, 252601, 252601, 252601, 1152271, 2508013, 2508013, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 6733693, 6733693, 6733693
Offset: 1

Views

Author

Robert G. Wilson v, May 06 2003

Keywords

Comments

Records: 341, 1105, 1729, 29341, 162401, 252601, 1152271, 2508013, 3828001, 6733693, 17098369, 17236801, 29111881, 82929001, 172947529, 216821881, 228842209, 366652201, .... - Robert G. Wilson v, May 11 2012
Conjecture: for n > 1, a(n) is the smallest Carmichael number k with lpf(k) > prime(n). It seems that such Carmichael numbers have exactly three prime factors. - Thomas Ordowski, Apr 18 2017
The conjecture is true if a(n) < A285549(n) for all n > 1. It holds for all a(n) < 2^64. - Max Alekseyev and Thomas Ordowski, Mar 13 2018
If prime(n) < m < a(n), then m is prime if and only if p^(m-1) == 1 (mod m) for every prime p <= prime(n). - Thomas Ordowski, Mar 05 2018
By this conjecture in the second comment, a(n) <= A135720(n+1), with equality for n > 1 iff a(n) < a(n+1), namely for n = 2, 3, 5, 6, 12, 13, 15, 25, 28, 29, ... For such n, a(n) gives all terms of A300629 > 561. - Thomas Ordowski, Mar 10 2018

Links

Crossrefs

Cf. A002997, A001567, A052155, A083737, A087788, A083739, A135720, A141768, A250199, A271221, A285549, A300629.

Programs

  • Mathematica
    k = 4; Do[l = Table[ Prime[i], {i, 1, n}]; While[ PrimeQ[k] || Union[PowerMod[l, k - 1, k]] != {1}, k++ ]; Print[k], {n, 1, 29}]
  • PARI
    isps(k, n) = {if (isprime(k), return (0)); my(nbok = 0); for (b=2, prime(n), if (Mod(b, k)^(k-1) == 1, nbok++, break)); if (nbok==prime(n)-1, return (1));}
a(n) = {my(k=2); while (!isps(k, n), k++); return (k);} \\ Michel Marcus, Apr 27 2018

A300629 a(1) = 561; a(n+1) = smallest Fermat pseudoprime to all natural bases up to lpf(a(n)).

Original entry on oeis.org

561, 1105, 1729, 29341, 162401, 252601, 1152271, 2508013, 3828001, 6733693, 17098369, 17236801, 29111881, 82929001, 172947529, 216821881, 228842209, 366652201, 413138881, 2301745249, 2438403661, 5255104513, 5781222721, 8251854001, 12173703001, 13946829751, 15906120889, 23224518901, 31876135201, 51436355851, 57274147841, 58094662081
Offset: 1

Views

Author

Thomas Ordowski, Mar 10 2018

Keywords

Comments

It is sufficient to consider only prime bases: a(n+1) is the least composite number k such that p^(k-1) == 1 (mod k) for every prime p <= lpf(a(n)), with a(1) = 561.
Conjecture: a(n+1) is the smallest Carmichael number k such that lpf(k) > lpf(a(n)), with a(1) = 561. It seems that such Carmichael numbers have exactly three prime factors.
The above conjecture is true if A083876(n) < A285549(n) for all n > 1, but has not been proven; there is no counterexample up to a(n) < 2^64. - Max Alekseyev and Thomas Ordowski, Mar 13 2018
Carl Pomerance (in a letter to the author) wrote, Mar 13 2018: (Start)
Assuming a strong form of the prime k-tuples conjecture, if there are no small counterexamples, there are likely to be none.
Here's why.
Assuming prime k-tuples, there are infinitely many Carmichael numbers of the form (6k+1)(12k+1)(18k+1), where each factor is prime. And from Bateman-Horn, these are fairly thickly distributed. There are other even better triples such as (60k+41)(90k+61)(150k+101), where "better" means the least prime factor is not so far below the cube root.
So, to get into the sequence, a number needs to be a Fermat pseudoprime for every base up to nearly the cube root.
However, it's a theorem that a sufficiently large number with this property must be a Carmichael number. (End)
Theorem: if lpf(a(n)) < m < a(n), then m is prime if and only if p^(m-1) == 1 (mod m) for every prime p <= lpf(a(n)). - Thomas Ordowski, Mar 13 2018
lpf(a(n)) are listed in A300748. - Max Alekseyev, Mar 13 2018
For m > 1, A135720(m) >= A083876(m-1), with equality iff lpf(a(n)) = prime(m); by this conjecture in the second comment. - Thomas Ordowski, Mar 13 2018

Links

Crossrefs

Cf. A002997, A020639, A083876, A271221, A285549, A300748.
Subsequence of A087788 and of A135720.

A300748 Least prime divisor of A300629(n).

Original entry on oeis.org

3, 5, 7, 13, 17, 41, 43, 53, 101, 109, 113, 151, 211, 281, 307, 331, 337, 461, 617, 727, 739, 827, 1033, 1301, 1481, 1531, 1723, 1901, 2161, 2351, 2381, 2633, 2647, 2801, 3371, 3931, 4933, 5653, 5743, 6791, 6917, 7561, 8059, 9521, 10369, 11503, 11551, 12161, 17579, 17839, 18433, 20593, 21061, 23581, 26731, 30241
Offset: 1

Views

Author

Max Alekseyev, Mar 11 2018

Keywords

Comments

For m > 2, A135720(m) = A083876(m-1) if and only if a(n) = prime(m).

Links

Crossrefs

Cf. A002997, A020639, A083876, A285549, A300629.

Formula

a(n) = A020639(A300629(n)).

A321790 a(n) is the smallest base a > 2 such that a^(k-1) != 1 (mod k), where k = A001567(n), the n-th Fermat pseudoprime to base 2.

Original entry on oeis.org

3, 3, 3, 5, 3, 7, 3, 3, 5, 5, 7, 3, 3, 3, 3, 3, 3, 7, 3, 3, 3, 7, 3, 5, 3, 3, 3, 3, 3, 3, 3, 7, 3, 3, 5, 3, 3, 3, 3, 13, 3, 3, 3, 3, 5, 3, 3, 3, 3, 7, 3, 3, 13, 5, 3, 7, 3, 3, 3, 3, 3, 7, 3, 3, 3, 3, 3, 11, 3, 5, 5, 3, 3, 3, 5, 5, 3, 5, 7, 5, 5, 3, 13, 3, 3
Offset: 1

Views

Author

Thomas Ordowski, Nov 19 2018

Keywords

Comments

a(n) <= A177415(n).
Each a(n) is an odd prime.
If k = A001567(n) is a Carmichael number, then a(n) = lpf(k).
Conjecture: if k = A001567(n) is semiprime, then a(n) < lpf(k).
The smallest numbers k = A001567(n) such that a(n) = prime(m) for m > 1 are 341, 1105, 1729, 75361, 29341, 162401, 334153, ... See A135720 > 561.
The smallest such semiprimes are 341, 2701, ?, 721801, ... Cf. A285549.

Examples

			The first Fermat pseudoprime to base 2 is 341, and 341 is not a Fermat pseudoprime to base 3, so a(1) = 3.

Crossrefs

Cf. A001567, A002997, A083876, A135720, A177415, A214305, A285549.
A141710 is a subsequence.

Programs

  • Mathematica
    a[p_] := Module[{m=3}, While[Mod[m^(p-1), p] == 1, m++]; m]; psp = Select[Range[3, 1000000, 2], CompositeQ[ # ] && PowerMod[2, (# - 1), # ] == 1 &]; Map[a, psp] (* Amiram Eldar, Nov 19 2018 *)

Extensions

More terms from Amiram Eldar, Nov 19 2018

A294179 a(n) is the smallest k with n prime factors such that p^k == p (mod k) for every prime p dividing k.

Original entry on oeis.org

2, 65, 561, 41041, 825265, 321197185, 5394826801, 232250619601, 9746347772161
Offset: 1

Views

Author

Thomas Ordowski, Feb 11 2018

Keywords

Comments

All the terms are squarefree. Are all composite terms odd?
Conjecture: the sequence contains only finitely many Carmichael numbers, A006931. What is the smallest n >= 3 for which a(n) is not a Carmichael number? For n >= 3, a(n) <= A006931(n).

Crossrefs

Cf. A006931, A285549, A294169.

Programs

  • Maple
    for k from 2 to 10^6 do
  if numtheory:-issqrfree(k) then
    ps := numtheory:-factorset(k);
    n := nops(ps);
    if not assigned(A[n]) and andmap(p -> p &^ k -p mod k = 0, ps) then
      A[n] := k;
    end if
  end if;
end do:
seq(A[i],i=1..max(map(op, [indices(A)]))); # Robert Israel, Feb 11 2018
  • Mathematica
    With[{s = Select[Range[10^6], Function[k, AllTrue[FactorInteger[k][[All, 1]], PowerMod[#, k, k] == Mod[#, k] &]]]}, Select[Table[SelectFirst[s, PrimeOmega@ # == n &], {n, 5}], IntegerQ]] (* Michael De Vlieger, Feb 20 2018 *)

Extensions

a(7)-a(8) from Daniel Suteu, Feb 06 2023
a(9) from Michael S. Branicky, Aug 03 2023

A354692 Smallest Euler-Jacobi pseudoprime to all natural bases up to prime(n) - 1 that is not a base prime(n) Euler-Jacobi pseudoprime.

Original entry on oeis.org

9, 561, 10585, 1729, 488881, 399001, 2433601, 1857241, 6189121, 549538081, 50201089, 14469841, 86566959361, 311963097601, 369838909441, 31929487861441, 6389476833601, 8493512837546881, 31585234281457921, 10120721237827201, 289980482095624321, 525025434548260801, 91230634325542321
Offset: 1

Views

Author

Jinyuan Wang, Jun 03 2022

Keywords

Comments

An Euler-Jacobi pseudoprime to the base b is an odd composite number k such that gcd(b, k) = 1 and the Jacobi symbol (.,.) satisfies b^((k-1)/2) == (b,k) (mod k).
a(n) is coprime to A002110(n-1).
a(24) > 2^64. - Daniel Suteu, Jun 05 2022

Links

Crossrefs

Cf. A002110, A007324, A047713, A285549, A354694.

Programs

  • PARI
    a(n) = my(b, p=factorback(primes(n-1))); forcomposite(k=9, oo, if(gcd(k, p)==1, b=2; while(Mod(b, k)^(k\2) == kronecker(b, k), b++); if(b==prime(n), return(k))));

Extensions

a(13)-a(23) from Daniel Suteu, Jun 05 2022
Showing 1-7 of 7 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.