"Fermat's little theorem" - cp's OEIS frontend

A143324 Table T(n,k) by antidiagonals. T(n,k) is the number of length n primitive (=aperiodic or period n) k-ary words (n,k >= 1).

1, 2, 0, 3, 2, 0, 4, 6, 6, 0, 5, 12, 24, 12, 0, 6, 20, 60, 72, 30, 0, 7, 30, 120, 240, 240, 54, 0, 8, 42, 210, 600, 1020, 696, 126, 0, 9, 56, 336, 1260, 3120, 4020, 2184, 240, 0, 10, 72, 504, 2352, 7770, 15480, 16380, 6480, 504, 0, 11, 90, 720, 4032, 16800, 46410, 78120, 65280, 19656, 990, 0

Offset: 1

Alois P. Heinz, Aug 07 2008

Column k is Dirichlet convolution of mu(n) with k^n.

The coefficients of the polynomial of row n are given by the n-th row of triangle A054525; for example row 4 has polynomial -k^2+k^4.

			T(2,3)=6, because there are 6 primitive words of length 2 over 3-letter alphabet {a,b,c}: ab, ac, ba, bc, ca, cb; note that the non-primitive words aa, bb and cc don't belong to the list; secondly note that the words in the list need not be Lyndon words, for example ba can be derived from ab by a cyclic rotation of the positions.
Table begins:
  1,  2,   3,    4,    5, ...
  0,  2,   6,   12,   20, ...
  0,  6,  24,   60,  120, ...
  0, 12,  72,  240,  600, ...
  0, 30, 240, 1020, 3120, ...

Alois P. Heinz, Antidiagonals n = 1..141, flattened
C. J. Smyth, A coloring proof of a generalisation of Fermat's little theorem, Amer. Math. Monthly 93, No. 6 (1986), pp. 469-471.
Lucas Vieira Barbosa, Nonclassical Temporal Correlations Under Finite-Memory Constraints, Doctoral Thesis, Univ. Wien (Austria 2024). See p. 35.
Index entries for sequences related to Lyndon words

Columns k=1-10 give: A000007(n-1), A027375, A054718, A054719, A054720, A054721, A218124, A218125, A218126, A218127.
Rows n=1-10 give: A000027, A002378(k-1), A007531(k+1), A047928(k+1), A061167, A218130, A133499, A218131, A218132, A218133.
Main diagonal gives A252764.
Cf. A074650, A143325, A008683, A054525.

with(numtheory): f0:= proc(n) option remember; unapply(k^n-add(f0(d)(k), d=divisors(n)minus{n}), k) end; T:= (n,k)-> f0(n)(k); seq(seq(T(n, 1+d-n), n=1..d), d=1..12);

f0[n_] := f0[n] = Function [k, k^n - Sum[f0[d][k], {d, Complement[Divisors[n], {n}]}]]; t[n_, k_] := f0[n][k]; Table[Table[t[n, 1 + d - n], {n, 1, d}], {d, 1, 12}] // Flatten (* Jean-François Alcover, Dec 12 2013, translated from Maple *)

T(n,k) = Sum_{d|n} k^d * mu(n/d).

T(n,k) = k^n - Sum_{d

T(n,k) = A143325(n,k) * k.

T(n,k) = A074650(n,k) * n.

So Sum_{d|n} k^d * mu(n/d) == 0 (mod n), this is a generalization of Fermat's little theorem k^p - k == 0 (mod p) for primes p to an arbitrary modulus n (see the Smyth link). - Franz Vrabec, Feb 09 2021

A220418 Express 1 - x - x^2 - x^3 - x^4 - ... as product (1 + g(1)x) (1 + g(2)x^2) (1 + g(3)x^3) ... and use a(n) = - g(n).

Original entry on oeis.org

1, 1, 2, 3, 6, 8, 18, 27, 54, 84, 186, 296, 630, 1008, 2106, 3711, 7710, 12924, 27594, 48528, 97902, 173352, 364722, 647504, 1340622, 2382660, 4918482, 9052392, 18512790, 33361776, 69273666, 127198287, 258155910, 475568220, 981288906, 1814542704, 3714566310

Offset: 1

Michel Marcus, Dec 14 2012

nonn

This is the PPE (power product expansion) of A153881 (with offset 0).
When p is prime, a(p) = (2^p-2)/p (A064535).
From Petros Hadjicostas, Oct 04 2019: (Start)
This sequence appears as an example in Gingold and Knopfmacher (1995) starting at p. 1223.
In Section 3 of Gingold and Knopfmacher (1995), it is proved that, if f(z) = Product_{n >= 1} (1 + g(n))*z^n = 1/(Product_{n >= 1} (1 - h(n))*z^n), then g(2*n - 1) = h(2*n - 1) and Sum_{d|n} (1/d)*h(n/d)^d = -Sum_{d|n} (1/d)*(-g(n/d))^d. The same results were proved more than ten years later by Alkauskas (2008, 2009). [If we let a(n) = -g(n), then Alkauskas works with f(z) = Product_{n >= 1} (1 - a(n))*z^n; i.e., a(2*n - 1) = -h(2*n - 1) etc.]
The PPE of 1/(1 - x - x^2 - x^3 - x^4 - ...) is given in A290261, which is also studied in Gingold and Knopfmacher (1995, p. 1234).
(End)
The number of terms in the Zassenhaus formula exponent of order n, as computed by the algorithm by Casas, Murua & Nadinic, is equal to a(n) at least for n = 2..24. - Andrey Zabolotskiy, Apr 09 2023

Alois P. Heinz, Table of n, a(n) for n = 1..2000
Giedrius Alkauskas, One curious proof of Fermat's little theorem, arXiv:0801.0805 [math.NT], 2008.
Giedrius Alkauskas, A curious proof of Fermat's little theorem, Amer. Math. Monthly 116(4) (2009), 362-364.
Fernando Casas, Ander Murua and Mladen Nadinic, Efficient computation of the Zassenhaus formula, Computer Physics Communications, 183 (2012), 2386-2391; arXiv:1204.0389 [math-ph], 2012.
H. Gingold, H. W. Gould, and Michael E. Mays, Power Product Expansions, Utilitas Mathematica 34 (1988), 143-161.
H. Gingold and A. Knopfmacher, Analytic properties of power product expansions, Canad. J. Math. 47 (1995), 1219-1239.
W. Lang, Recurrences for the general problem.

Cf. A064535, A147541, A153881, A157162, A170908, A170909, A170910, A170911, A170912, A170913, A170914, A170915, A170916, A170917, A220420, A273866, A290261.

b:= proc(n, i) option remember; `if`(n=0 or i<1, 1,
      b(n, i-1)+a(i)*b(n-i, min(n-i, i)))
    end:
a:= proc(n) option remember; 2^n-b(n, n-1) end:
seq(a(n), n=1..40);  # Alois P. Heinz, Jun 22 2018

b[n_, i_] := b[n, i] = If[n == 0 || i < 1, 1, b[n, i - 1] + a[i]*b[n - i, Min[n - i, i]]];
a[n_] := a[n] = 2^n - b[n, n - 1] ;
Array[a, 40] (* Jean-François Alcover, Jul 09 2018, after Alois P. Heinz *)

a(m) = {default(seriesprecision, m+1); gk = vector(m); pol = 1 + sum(n=1, m, -x^n); gk[1] = polcoeff( pol, 1); for (k=2, m, pol = taylor(pol/(1+gk[k-1]*x^(k-1)), x); gk[k] = polcoeff(pol, k, x);); for (k=1, m, print1(-gk[k], ", "););}

g(1) = -1 and for k > 1, g(k) satisfies Sum_{d|k} (1/d)*(-g(k/d))^d = (2^k - 1)/k, where a(k) = -g(k). - Gevorg Hmayakyan, Jun 05 2016 [Corrected by Petros Hadjicostas, Oct 04 2019. See p. 1224 in Gingold and Knopfmacher (1995).]
From Petros Hadjicostas, Oct 04 2019: (Start)
a(2*n - 1) = A290261(2*n - 1) for n >= 1 because A290261 gives the PPE of 1/(1 - x - x^2 - x^3 - ...) = (1 - x)/(1 - 2*x).
Define (A(m,n): n,m >= 1) by A(m=1,n) = -1 for n >= 1, A(m,n) = 0 for m > n >= 1 (upper triangular), and A(m,n) = A(m-1,n) - A(m-1,m-1) * A(m,n-m+1) for n >= m >= 2. Then a(n) = A(n,n). [Theorem 3 in Gingold et al. (1988).]
(End)

Name edited by Petros Hadjicostas, Oct 04 2019

A001897 Denominators of cosecant numbers: -2(2^(2n-1)-1)Bernoulli(2n).

Original entry on oeis.org

1, 3, 15, 21, 15, 33, 1365, 3, 255, 399, 165, 69, 1365, 3, 435, 7161, 255, 3, 959595, 3, 6765, 903, 345, 141, 23205, 33, 795, 399, 435, 177, 28393365, 3, 255, 32361, 15, 2343, 70050435, 3, 15, 1659, 115005, 249, 1702155, 3, 30705, 136059, 705, 3, 2250885, 3, 16665, 2163

Offset: 0

N. J. A. Sloane

Same as half the denominators of the even-indexed Bernoulli numbers B_{2*n} for n>0, by the von Staudt-Clausen theorem and Fermat's little theorem. - Bernd C. Kellner and Jonathan Sondow, Jan 02 2017 [This is implemented in the second Maple program. - Peter Luschny, Aug 21 2021]

			Cosecant numbers {-2*(2^(2*n-1)-1)*Bernoulli(2*n)} are 1, -1/3, 7/15, -31/21, 127/15, -2555/33, 1414477/1365, -57337/3, 118518239/255, -5749691557/399, 91546277357/165, -1792042792463/69, 1982765468311237/1365, -286994504449393/3, 3187598676787461083/435, ... = A001896/A001897.

H. T. Davis, Tables of the Mathematical Functions. Vols. 1 and 2, 2nd ed., 1963, Vol. 3 (with V. J. Fisher), 1962; Principia Press of Trinity Univ., San Antonio, TX, Vol. 2, p. 187.
S. A. Joffe, Sums of like powers of natural numbers, Quart. J. Pure Appl. Math. 46 (1914), 33-51.
N. E. Nörlund, Vorlesungen über Differenzenrechnung. Springer-Verlag, Berlin, 1924, p. 458.
J. Riordan, Combinatorial Identities, Wiley, 1968, p. 199. See Table 3.3.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Hector Blandin and Rafael Diaz, Compositional Bernoulli numbers, arXiv:0708.0809 [math.CO], 2007-2008, Page 7, 3rd table, (B^sin)_1,n is identical to |A001896| / A001897.
S. A. Joffe, Sums of like powers of natural numbers, Quart. J. Pure Appl. Math. 46 (1914), 33-51. [Annotated scanned copy of pages 38-51 only, plus notes]
Masanobu Kaneko, Maneka Pallewatta, and Hirofumi Tsumura, On Polycosecant Numbers, J. Integer Seq. 23 (2020), no. 6, 17 pp. See line k=1 of Table 1 p. 3.
D. H. Lehmer, Lacunary recurrence formulas for the numbers of Bernoulli and Euler, Annals Math., 36 (1935), 637-649.
N. E. Nörlund, Vorlesungen über Differenzenrechnung, Springer 1924, p. 27.
N. E. Nörlund, Vorlesungen über Differenzenrechnung, Springer-Verlag, Berlin, 1924 [Annotated scanned copy of pages 144-151 and 456-463]

Cf. A001896 (numerators), A027642, A033469, A160014, A241171, A277087, A340556.

Cf. A132092-A132099,

[Denominator(2*(1-2^(2*n-1))*Bernoulli(2*n)): n in [0..55]]; // G. C. Greubel, Apr 06 2019

b := n -> bernoulli(n)*2^add(i,i=convert(n,base,2));
a := n -> denom(b(2*n)); # Peter Luschny, May 02 2009
# Alternative :
Clausen := proc(n) local i,S; map(i->i+1, numtheory[divisors](n));
S := select(isprime, %); if S <> {} then mul(i,i=S) else NULL fi end:
A001897_list := n -> [1,seq(Clausen(2*i)/2,i=1..n-1)];
A001897_list(52); # Peter Luschny, Oct 03 2011

a[n_] := Denominator[-2*(2^(2*n-1)-1)*BernoulliB[2*n]]; Table[a[n], {n, 0, 55}] (* Jean-François Alcover, Sep 11 2013 *)

a(n) = denominator(-2*(2^(2*n-1)-1)*bernfrac(2*n)); \\ Michel Marcus, Apr 06 2019

def A001897(n):
    if n == 0:
        return 1
    M = (d + 1 for d in divisors(2 * n))
    return prod(s for s in M if is_prime(s)) / 2
[A001897(n) for n in range(55)]  # Peter Luschny, Feb 20 2016

a(0)=1, a(n)=(1/2)*A002445(n) for n>=1. - Joerg Arndt, May 07 2012
a(n) = denominator((2*n)!*Li_{2*n}(1)) for n > 0. - Peter Luschny, Jun 29 2012
a(0)=1, a(n) = (1/2)*A027642(2*n) = (3/2)*A277087(n) for n>=1. - Jonathan Sondow, Dec 14 2016
From Peter Luschny, Sep 06 2017: (Start)
a(n) = denominator(r(n)) where r(n) = Sum_{0..n} (-1)^(n-k)*A241171(n, k)/(2*k+1).
a(n) = denominator(bernoulli(2*n, 1/2))/4^n = A033469(n)/4^n. (End)
Apparently a(n) = denominator(Sum_{k=0..2*n-2} (-1)^k*E2(2*n-1, k+1)/binomial(4*n-1, k+1)), where E2(n, k) denotes the second-order Eulerian numbers A340556. - Peter Luschny, Feb 17 2021

A031974 1 repeated prime(n) times.

Original entry on oeis.org

11, 111, 11111, 1111111, 11111111111, 1111111111111, 11111111111111111, 1111111111111111111, 11111111111111111111111, 11111111111111111111111111111, 1111111111111111111111111111111, 1111111111111111111111111111111111111

Offset: 1

J. Castillo (arp(AT)cia-g.com) [Broken email address?]

Salomaa's first example of an infinite language. - N. J. A. Sloane, Dec 05 2012
If p is a prime and gcd(p,b-1)=1, then (b^p-1)/(b-1) == 1 (mod p); by Fermat's little theorem. For example 1111111 == 1 (mod 7). - Thomas Ordowski, Apr 09 2016
Also Mersenne numbers (A001348) written in binary. - Kritsada Moomuang, May 13 2025

A. Salomaa, Jewels of Formal Language Theory. Computer Science Press, Rockville, MD, 1981, p. 2. - From N. J. A. Sloane, Dec 05 2012

N. J. A. Sloane, Table of n, a(n) for n = 1..50
Fanel Iacobescu, Smarandache Partition Type Sequences, in Bulletin of Pure and Applied Sciences, India, Vol. 16E, No. 2, 1997, pp. 237-240
M. Le and K. Wu, The Primes in the Smarandache Unary Sequence, Smarandache Notions Journal, Vol. 9, No. 1-2. 1998, 98-99.
Eric Weisstein's World of Mathematics, Smarandache Sequences

A004022 is the subsequence of primes. - Jeppe Stig Nielsen, Sep 14 2014

Cf. A001348.

[(10^p-1)/9: p in PrimesUpTo(40)]; // Vincenzo Librandi, May 29 2014

f:=n->(10^ithprime(n)-1)/9; [seq(f(n),n=1..20)]; # N. J. A. Sloane, Dec 05 2012

Table[FromDigits[PadRight[{},Prime[n],1]],{n,15}] (* Harvey P. Dale, Apr 10 2012 *)

a(n) = A000042(A000040(n)). - Jason Kimberley, Dec 19 2012

a(n) = (10^prime(n) - 1)/9. - Vincenzo Librandi, May 29 2014

More terms from Erich Friedman

Corrected and extended by Harvey P. Dale, Apr 10 2012

A157162 1/Product_{n>=1} (1 - a(n)x^n) = 1 + Sum_{k>=1} F(k+1)x^k = 1/(1-x-x^2), where F(n) = A000045(n) (Fibonacci numbers).

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 4, 5, 8, 10, 18, 24, 40, 52, 88, 125, 210, 286, 492, 702, 1144, 1638, 2786, 3986, 6704, 9640, 16096, 23964, 39650, 57794, 97108, 144245, 236880, 353010, 589298, 880828, 1459960, 2179068, 3604880, 5471094, 9030450, 13561742, 22542396, 34277634

Offset: 1

Wolfdieter Lang, Aug 10 2009

A formal infinite product representation for the o.g.f. series of the Fibonacci numbers (A000045).
In the context of Witt rings the o.g.f. is called associated unital series for the (infinite dimensional) Witt vector (a(1),a(2),...). Sometimes also called inverse Somos transform, here for the Fibonacci numbers.
1-x-x^2 = product(1 - a(n)*x^n, n=1..infinity).

			Recurrence I: a(2) = F(3) - a(1)^2 = 1; a(4) = F(5) - (a(1)*a(3) + a(2)^2 +a(1)^2*a(2) + a(1)^4) = 5 - 4 = 1.
Recurrence II (simplified): a(4) = (-(a(1)^4 + 2*a(2)^2) + L(4))/4 = (-3 + 7)/4 = 1.
Recurrence II: a(4)= (-(a(1)^4 + 2*a(2)^2)/4 + 1*1*F(5) - (1/2)*(2*F(2)*F(4)+ 1*F(3)^2) +(1/3)*3*F(2)^2*F(3)-(1/4)*1*F(2)^4 = -3/4 +7/4 = 1.

Alois P. Heinz, Table of n, a(n) for n = 1..2000
Giedrius Alkauskas, One curious proof of Fermat's little theorem, arXiv:0801.0805 [math.NT], 2008.
Giedrius Alkauskas, A curious proof of Fermat's little theorem, Amer. Math. Monthly 116(4) (2009), 362-364.
Giedrius Alkauskas, Algebraic functions with Fermat property, eigenvalues of transfer operator and Riemann zeros, and other open problems, arXiv:1609.09842 [math.NT], 2016.
H. Gingold, H. W. Gould, and Michael E. Mays, Power Product Expansions, Utilitas Mathematica 34 (1988), 143-161.
H. Gingold and A. Knopfmacher, Analytic properties of power product expansions, Canad. J. Math. 47 (1995), 1219-1239.
Wolfdieter Lang, Recurrences for the general problem.

Cf. A147542 (with the product instead of the reciprocal one).

Cf. A220418.

a[n_] := a[n] = If[n == 1, 1, (-Sum[d a[d]^(n/d), {d, Most@ Divisors@ n}] + LucasL[n])/n];
Array[a, 50] (* Jean-François Alcover, Mar 02 2020 *)

Recurrence I. With P(n,m) the set of partitions of n with m parts:
a(n)= F(n+1) - sum(sum(product(a(j)^e(j),j=1..m), p from P(n,m)), m=2..n), n>=2, with sum(j*e(j),j=1..n)=n, sum(e(j),j=1..n)=m for the partition p of n with m parts. F(n) = A000045(n) (Fibonacci numbers). Input a(1)=F(2)=1. See the array A008284(n,m) for the cardinalities of the sets P(n,m).
Recurrence II (simplified version). With the Lucas numbers L(n)=A000035(n), n>=1, as input (found by V. Jovovic, Mar 10 2009):
a(n) = (- sum(d*a(d)^(n/d), d|n with 1<=d=2, a(1)=1.
Recurrence II. With the number array M0(n,vec(e)) given for any partition in A048996.
a(n) = - sum((d/n)*(a(d))^(n/d),d|n with 1<=d=2; a(1)=F(2)=1. See recurrence 1 for the set P(n,m). The M0 numbers are m!/product(e(j)!,j=1..n).

A005936 Pseudoprimes to base 5.

Original entry on oeis.org

4, 124, 217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611, 5662, 5731, 6601, 7449, 7813, 8029, 8911, 9881, 11041, 11476, 12801, 13021, 13333, 13981, 14981, 15751, 15841, 16297, 17767, 21361, 22791, 23653, 24211, 25327, 25351, 29341, 29539

Offset: 1

N. J. A. Sloane

nonn

According to Karsten Meyer, 4 should be excluded, following the strict definition in Crandall and Pomerance. - May 16 2006
Theorem: If both numbers q and (2q - 1) are primes (q is in the sequence A005382) then n = q*(2q - 1) is a pseudoprime to base 5 (n is in the sequence) if and only if q is of the form 10k + 1. 1891, 88831, 146611, 218791, 721801, ... are such terms. This sequence is a subsequence of A122782. - Farideh Firoozbakht, Sep 14 2006
Composite numbers n such that 5^(n-1) == 1 (mod n).

R. Crandall and C. Pomerance, "Prime Numbers - A Computational Perspective", Second Edition, Springer Verlag 2005, ISBN 0-387-25282-7 Page 132 (Theorem 3.4.2. and Algorithm 3.4.3)
J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 124, p. 43, Ellipses, Paris 2008.
R. K. Guy, Unsolved Problems in Number Theory, A12.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. J. Mathar, T. D. Noe and Hiroaki Yamanouchi, Table of n, a(n) for n = 1..92893 (terms a(1)-a(776) from R. J. Mathar, a(777)-a(1000) from T. D. Noe)
J. Bernheiden, Pseudoprimes (Text in German)
C. Pomerance & N. J. A. Sloane, Correspondence, 1991
F. Richman, Primality testing with Fermat's little theorem
Eric Weisstein's World of Mathematics, Fermat Pseudoprime
Index entries for sequences related to pseudoprimes

Pseudoprimes to other bases: A001567 (2), A005935 (3), A005937 (6), A005938 (7), A005939 (10).

Cf. A005382, A122782.

base = 5; t = {}; n = 1; While[Length[t] < 100, n++; If[! PrimeQ[n] && PowerMod[base, n-1, n] == 1, AppendTo[t, n]]]; t (* T. D. Noe, Feb 21 2012 *)
Select[Range[30000],CompositeQ[#]&&PowerMod[5,#-1,#]==1&] (* Harvey P. Dale, Jul 21 2023 *)

More terms from David W. Wilson, Aug 15 1996

A005938 Pseudoprimes to base 7.

Original entry on oeis.org

6, 25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, 8321, 10225, 10585, 10621, 11041, 11521, 12025, 13665, 14089, 16725, 16806, 18721, 19345, 20197, 20417, 20425, 22945, 25829, 26419, 29234, 29341, 29857, 29891, 30025, 30811, 33227

Offset: 1

N. J. A. Sloane

nonn

According to Karsten Meyer, May 16 2006, 6 should be excluded, following the strict definition in Crandall and Pomerance.
Theorem: If both numbers q & 2q-1 are primes(q is in the sequence A005382) and n=q*(2q-1) then 7^(n-1)==1 (mod 7)(n is in the sequence) iff q=2 or mod(q,14) is in the set {1, 5, 13}. 6,703,18721,38503,88831,104653,146611,188191,... are such terms. This sequence is a subsequence of A122784. - Farideh Firoozbakht, Sep 14 2006
Composite numbers n such that 7^(n-1) == 1 (mod n).

R. Crandall and C. Pomerance, "Prime Numbers - A Computational Perspective", Second Edition, Springer Verlag 2005, ISBN 0-387-25282-7 Page 132 (Theorem 3.4.2. and Algorithm 3.4.3)
R. K. Guy, Unsolved Problems in Number Theory, A12.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. J. Mathar, T. D. Noe and Hiroaki Yamanouchi, Table of n, a(n) for n = 1..87448 (terms a(1)-a(697) from R. J. Mathar, a(698)-a(1000) from T. D. Noe)
J. Bernheiden, Pseudoprimes (Text in German)
C. Pomerance & N. J. A. Sloane, Correspondence, 1991
F. Richman, Primality testing with Fermat's little theorem
Index entries for sequences related to pseudoprimes

Pseudoprimes to other bases: A001567 (2), A005935 (3), A005936 (5), A005937 (6), A005939 (10).

Cf. A005382, A122784.

Select[Range[31000], ! PrimeQ[ # ] && PowerMod[7, (# - 1), # ] == 1 &] (* Farideh Firoozbakht, Sep 14 2006 *)

from sympy import isprime
def ok(n): return pow(7, n-1, n) == 1 and not isprime(n)
print(list(filter(ok, range(1, 34000)))) # Michael S. Branicky, Jun 25 2021

A097933 Primes p that divide 3^((p-1)/2) - 1.

Original entry on oeis.org

11, 13, 23, 37, 47, 59, 61, 71, 73, 83, 97, 107, 109, 131, 157, 167, 179, 181, 191, 193, 227, 229, 239, 241, 251, 263, 277, 311, 313, 337, 347, 349, 359, 373, 383, 397, 409, 419, 421, 431, 433, 443, 457, 467, 479, 491, 503, 541, 563, 577, 587, 599, 601, 613

Offset: 1

Cino Hilliard, Sep 04 2004

nonn

Rational primes that decompose in the field Q[sqrt(3)]. - N. J. A. Sloane, Dec 26 2017
For all primes p > 2 and integers gcd(x, y, p) = 1, x^((p-1)/2) +- y^((p-1)/2) is divisible by p. This is because (x^((p-1)/2) - y^((p-1)/2))(x^((p-1)/2) + y^((p-1)/2)) = x^(p-1) - y^(p-1) is divisible by p according to Fermat's Little Theorem (FLT). This sequence lists p that divides 3^((p-1)/2) - 1^((p-1)/2), and A003630 lists the '+' case.
Apart from initial terms, this and A038874 are the same. - N. J. A. Sloane, May 31 2009
Primes in A091998. - Reinhard Zumkeller, Jan 07 2012
Also, primes congruent to 1 or 11 (mod 12). - Vincenzo Librandi, Mar 23 2013
Conjecture: Let r(n) = (a(n) - 1)/(a(n) + 1) if a(n) mod 4 = 1, (a(n) + 1)/(a(n) - 1) otherwise; then Product_{n>=1} r(n) = (6/5) * (6/7) * (12/11) * (18/19) * ... = 2/sqrt(3). - Dimitris Valianatos, Mar 27 2017
Primes p such that Kronecker(12,p) = +1 (12 is the discriminant of Q[sqrt(3)]), that is, odd primes that have 3 as a quadratic residue. - Jianing Song, Nov 21 2018
Comment from Richard R. Forberg, Feb 07 2023: (Start)
Conjecture: These are the exclusive prime factors of the set of integers d > 1 such that there exist primitive Heronian triangles with sides {b, b+d, b+2d} for one or more integers b.
Also b is always > d. For d=11 the b values begin {15, 17, 65, 75, 267, 305, 1025, ...}. For d=1 (not prime, thus not listed) the b values are given by A016064. (End)

			For p = 5, 3^2 - 1 = 8 <> 3*k for any integer k, so 5 is not in this sequence.
For p = 11, 3^5 - 1 = 242 = 11*22, so 11 is in this sequence.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Index to sequences related to decomposition of primes in quadratic fields

Cf. A003630, A010051, A038874, A091998.

a097933 n = a097933_list !! (n-1)
a097933_list = [x | x <- a091998_list, a010051 x == 1]
-- Reinhard Zumkeller, Jan 07 2012

[p: p in PrimesUpTo(1000) | p mod 24 in [1, 11, 13, 23]]; // Vincenzo Librandi, Mar 23 2013

Select[Prime[Range[300]], MemberQ[{1, 11, 13, 23}, Mod[#, 24]]&] (* Vincenzo Librandi, Mar 23 2013 *)
Select[Prime[Range[2,200]],PowerMod[3,(#-1)/2,#]==1&] (* Harvey P. Dale, Jun 02 2020 *)

/* s = +-1, d=diff */ ptopm1d2(n,x,d,s) = { forprime(p=3,n,p2=(p-1)/2; y=x^p2 + s*(x-d)^p2; if(y%p==0,print1(p","))) }

{a(n)= local(m, c); if(n<1, 0, c=0; m=0; while( cMichael Somos, Aug 28 2006 */

A133613 Decimal digits such that for all k >= 1, the number A(k) := Sum_{n = 0..k-1} a(n)*10^n satisfies the congruence 3^A(k) == A(k) (mod 10^k).

Original entry on oeis.org

7, 8, 3, 5, 9, 1, 4, 6, 4, 2, 6, 2, 7, 2, 6, 5, 7, 5, 4, 0, 1, 9, 5, 0, 9, 3, 4, 6, 8, 1, 5, 8, 4, 8, 1, 0, 7, 6, 9, 3, 2, 7, 8, 4, 3, 2, 2, 2, 3, 0, 0, 8, 3, 6, 6, 9, 4, 5, 0, 9, 7, 6, 9, 3, 9, 9, 8, 1, 6, 9, 9, 3, 6, 9, 7, 5, 3, 5, 2, 6, 5, 1, 5, 8, 3, 9, 1, 8, 1, 0, 5, 6, 2, 8, 4, 2, 4, 0, 4, 9, 8, 0, 5, 1, 6

Offset: 0

Daniel Geisler (daniel(AT)danielgeisler.com), Dec 18 2007

10-adic expansion of the iterated exponential 3^^n for sufficiently large n (where c^^n denotes a tower of c's of height n). E.g., for n>9, 3^^n == 4195387 (mod 10^7).
This sequence also gives many final digits of Graham's number ...399618993967905496638003222348723967018485186439059104575627262464195387. - Paul Muljadi, Sep 08 2008 and J. Luis A. Yebra, Dec 22 2008
Graham's number can be represented as G(64):=3^^3^^...^^3 [see M. Gardner and Wikipedia], in which case its G(63) lowermost digits are guaranteed to match this sequence (i.e., the convergence speed of the base 3 is unitary - see A317905). To avoid such confusion, it would be best to interpret this sequence as a real-valued constant 0.783591464..., corresponding to 3^^k in the limit of k->infinity, and call it Graham's constant G(3). Generalizations to G(n) and G(n,base) are obvious. - Stanislav Sykora, Nov 07 2015
Let G(64) be Graham's number. Let b and c be two (strictly) positive integers so that the super-logarithm base b of c (i.e., slog_b(c)) is well defined. Then, this sequence gives the slog_3(G(64))-1 final digits of G(64) since the congruence speed of 3 is equal to 0 at height 1 while it is 1 for all the integer hyperexponents above 0 (i.e., 3 is characterized by a constant congruence speed of 1, as proved by Lemma 1 of "On the congruence speed of tetration" and also confirmed by Equation (16) of "Number of stable digits of any integer tetration" - see Links). On the other hand, the difference between the slog_3(G(64))-th rightmost digit of G(64) and a(slog_3(G(64))) is congruent to 6 modulo 10 (since the asymptotic phase shift of 3 is [4,6] - see A376842). - Marco Ripà, Oct 17 2024

			783591464262726575401950934681584810769327843222300836694509769399816993697535...
Consider the sequence 3^^n: 1, 3, 27, 7625597484987, ... From 3^^3 = 7625597484987 onwards, all terms end with the digits 87. This follows from Euler's generalization of Fermat's little theorem.

M. Gardner, Mathematical Games, Scientific American 237, 18 - 28 (1977).
M. Ripà, La strana coda della serie n^n^...^n, Trento, UNI Service, Nov 2011, p. 11-12, 69-78. ISBN 978-88-6178-789-6.
Ilan Vardi, "Computational Recreations in Mathematica," Addison-Wesley Publishing Co., Redwood City, CA, 1991, pages 226-229.

Robert G. Wilson v, Table of n, a(n) for n = 0..10039
J. Jimenez Urroz and J. Luis A. Yebra, On the equation a^x == x (mod b^n), J. Int. Seq. 12 (2009) #09.8.8.
Robert P. Munafo, Large Numbers [From _Robert G. Wilson v_, May 07 2010]
Reddit user atticdoor, Spotted an error in the comments of sequence A133613.
Marco Ripà, On the constant congruence speed of tetration, Notes on Number Theory and Discrete Mathematics, Volume 26, 2020, Number 3, Pages 245—260.
Marco Ripà, The congruence speed formula, Notes on Number Theory and Discrete Mathematics, 2021, 27(4), 43-61.
Wikipedia, Graham's number

Cf. A133612, A133614, A133615, A133616, A133617, A133618, A133619, A144539, A144540, A144541, A144542, A144543, A144544, A317905, A318478, A373387, A376842.

(* Import Mmca coding for "SuperPowerMod" and "LogStar" from text file in A133612 and then *) $RecursionLimit = 2^14; f[n_] := SuperPowerMod[3, n + 1, 10^n]; Reverse@ IntegerDigits@ f@ 105 (* Robert G. Wilson v, Mar 06 2014 *)

a(n) = floor( A183613(n+1) / 10^n ).

More terms from J. Luis A. Yebra, Dec 12 2008
Edited by N. J. A. Sloane, Dec 22 2008
More terms from Robert G. Wilson v, May 07 2010

Previous Showing 21-30 of 141 results. Next

cp's OEIS Frontend

A007535 Smallest pseudoprime ( > n ) to base n: smallest composite number m > n such that n^(m-1)-1 is divisible by m.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Extensions

A143324 Table T(n,k) by antidiagonals. T(n,k) is the number of length n primitive (=aperiodic or period n) k-ary words (n,k >= 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A220418 Express 1 - x - x^2 - x^3 - x^4 - ... as product (1 + g(1)*x) * (1 + g(2)*x^2) *(1 + g(3)*x^3) * ... and use a(n) = - g(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A001897 Denominators of cosecant numbers: -2*(2^(2*n-1)-1)*Bernoulli(2*n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

A031974 1 repeated prime(n) times.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

Extensions

A157162 1/Product_{n>=1} (1 - a(n)*x^n) = 1 + Sum_{k>=1} F(k+1)*x^k = 1/(1-x-x^2), where F(n) = A000045(n) (Fibonacci numbers).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A220418 Express 1 - x - x^2 - x^3 - x^4 - ... as product (1 + g(1)x) (1 + g(2)x^2) (1 + g(3)x^3) ... and use a(n) = - g(n).

A001897 Denominators of cosecant numbers: -2(2^(2n-1)-1)Bernoulli(2n).

A157162 1/Product_{n>=1} (1 - a(n)x^n) = 1 + Sum_{k>=1} F(k+1)x^k = 1/(1-x-x^2), where F(n) = A000045(n) (Fibonacci numbers).