A015910 -id:A015910 - cp's OEIS frontend

A036236 Least inverse of A015910: smallest integer k > 0 such that 2^k mod k = n, or 0 if no such k exists.

1, 0, 3, 4700063497, 6, 19147, 10669, 25, 9, 2228071, 18, 262279, 3763, 95, 1010, 481, 20, 45, 35, 2873, 2951, 3175999, 42, 555, 50, 95921, 27, 174934013, 36, 777, 49, 140039, 56, 2463240427, 110, 477, 697, 91, 578, 623, 156, 2453, 540923, 55, 70, 345119, 287

Offset: 0

David W. Wilson

a(1) = 0, that is, no n exists with 2^n mod n = 1. Proof: Assume that there exists such n > 1. Consider its smallest prime divisor p. Then 2^n == 1 (mod p) implying that the multiplicative order ord_p(2) divides n. However, since ord_p(2) < p and p is the smallest divisor of n, we have ord_p(2) = 1, that is, p divides 2^1 - 1 = 1 which is impossible. - Max Alekseyev
_Labos Elemer_ asked on Sep 27 2001 if all numbers > 1 eventually appear in A015910, that is, if a(n) > 0 for n > 1.
Ron Graham's conjecture from 1960 states that for any n > 1 there are infinitely many solutions to 2^k mod k = n. - Max Alekseyev, Oct 19 2024
Obviously k > n. - Daniel Forgues, Jul 06 2015

			n = 0: 2^1 mod 1 = 0, a(0) = 1;
n = 1: 2^k mod k = 1, no such k exists, so a(1) = 0;
n = 2: 2^3 mod 3 = 2, a(2) = 3;
n = 3: 2^4700063497 mod 4700063497 = 3, a(3) = 4700063497.

P. Erdős and R. L. Graham, Old and new problems and results in combinatorial number theory, Monographies de L'Enseignement Mathématique, 28, 1980.
R. K. Guy, Unsolved Problems in Number Theory, Section F10.

David W. Wilson, Table of n, a(n) for n = 0..1026 (from the Havermann file)
Joe K. Crump, 2^n mod n
Hans Havermann, Table of n, a(n) for n = 1..10000 with -1 for those entries where a(n) is unknown
Nick Hobson, Table of n, a(n) for n = 1..10000 with -1 for those entries where a(n) is unknown. [With 101 new terms and 2 corrections, this supersedes the earlier table from Hans Havermann. The corrections are to terms a(799) and a(881), where smaller values of k were found.]
Nick Hobson, C program
Eric Weisstein's World of Mathematics, 2

Cf. A015910, A015948, A078457, A119678, A119679, A127816, A119715, A119714, A127817, A127818, A127819, A127820, A127821.

Bisections: A122182, A124977.

a = Table[0, {75} ]; Do[ b = PowerMod[2, n, n]; If[b < 76 && a[[b]] == 0, a[[b]] = n], {n, 1, 5*10^9} ]; a
(* Second program: *)
t = Table[0, {1000} ]; k = 1; While[ k < 6500000000, b = PowerMod[2, k, k]; If[b < 1001 && t[[b]] == 0, t[[b]] = k]; k++ ]; t
nk[n_] := Module[ {k}, k = 1; While[PowerMod[2, k, k] != n, k++]; k]
Join[{1, 0}, Table[nk[i], {i, 2, 46}]]  (* Robert Price, Oct 11 2018 *)

a(n)=if(n==1,return(0));my(k=n);while(lift(Mod(2,k)^k)!=n,k++);k \\ Charles R Greathouse IV, Oct 12 2011

It's obvious that for each k, a(k) > k and we can easily prove that 2^(3^n) = 3^n-1 (mod 3^n). So 3^n is the least k with 2^k mod k = 3^n-1. Hence for each n, a(3^n-1) = 3^n. - Farideh Firoozbakht, Nov 14 2006

a(3) was first computed by the Lehmers.
More terms from Joe K. Crump (joecr(AT)carolina.rr.com), Sep 04 2000
a(69) = 887817490061261 = 29 * 37 * 12967 * 63809371. - Hagen von Eitzen, Jul 26 2009
Edited by Max Alekseyev, Jul 29 2011

A372707 Smallest natural number requiring n applications of the map x -> 2^x mod x = A015910(x) to reach 0.

Original entry on oeis.org

0, 1, 3, 18, 35, 207, 774, 1513, 2051, 8900, 13459, 25907, 34305, 88036, 153839, 382283, 397590, 636459, 844177, 1456073, 2426735, 7312307, 11716125, 14657311, 43165242, 52706549, 84955821, 188736643, 416569989, 953350161, 1617152961, 2541237149, 4847485412

Offset: 0

Bryle Morga, May 11 2024

nonn

A015910 is conjectured to contain every natural number except for 1, which would imply that this sequence has infinitely many terms.

Kevin Ryde, Table of n, a(n) for n = 0..45
Kevin Ryde, C Code

Cf. A015910.

C
```
/* See links. */
```

i = 0
c = [0]
for j in range(10**9):
    if c[-1] == i:
        print(f"a({i}) = {j}")
        i += 1
    c.append(1+c[pow(2, len(c), len(c))])

a(30)-a(32) from Michael S. Branicky, May 12 2024

A180075 If A015910(m) is a power of 2, append log_2(A015910(m)) to the sequence.

Original entry on oeis.org

1, 1, 2, 1, 3, 2, 1, 2, 1, 2, 3, 1, 1, 4, 3, 2, 1, 4, 2, 4, 1, 2, 1, 3, 2, 1, 2, 3, 4, 1, 1, 4, 2, 1, 4, 3, 4, 1, 5, 3, 2, 1, 4, 1, 2, 3, 5, 6, 1, 4, 3, 1, 6, 1, 2, 4, 6, 1, 4, 2, 1, 6, 5, 5, 3, 1

Offset: 1

Juri-Stepan Gerasimov, Jan 14 2011

nonn

Cf. A000079, A015910.

f[n_] := Log2@ PowerMod[2, n, n]; Select[f@ Range@ 100, IntegerQ]

A015910(m)=2^(a(n)).

A062173 a(n) = 2^(n-1) mod n.

Original entry on oeis.org

0, 0, 1, 0, 1, 2, 1, 0, 4, 2, 1, 8, 1, 2, 4, 0, 1, 14, 1, 8, 4, 2, 1, 8, 16, 2, 13, 8, 1, 2, 1, 0, 4, 2, 9, 32, 1, 2, 4, 8, 1, 32, 1, 8, 31, 2, 1, 32, 15, 12, 4, 8, 1, 14, 49, 16, 4, 2, 1, 8, 1, 2, 4, 0, 16, 32, 1, 8, 4, 22, 1, 32, 1, 2, 34, 8, 9, 32, 1, 48, 40, 2, 1, 32, 16, 2, 4, 40, 1, 32, 64, 8, 4, 2, 54, 32, 1, 58, 58, 88, 1, 32, 1, 24, 46

Offset: 1

Henry Bottomley, Jun 12 2001

nonn

If p is an odd prime then a(p)=1. However, a(n) is also 1 for pseudoprimes to base 2 such as 341.

			a(5) = 2^(5-1) mod 5 = 16 mod 5 = 1.

Antti Karttunen, Table of n, a(n) for n = 1..101101 (first 1000 terms from Harry J. Smith)
Index entries for sequences related to pseudoprimes

Cf. A000079, A001567, A015910, A015919, A062172.
Cf. A082495, A106262, A257531, A305890.
Cf. A176997 (after the initial term, gives the positions of ones).

import Math.NumberTheory.Moduli (powerMod)
a062173 n = powerMod 2 (n - 1) n  -- Reinhard Zumkeller, Oct 17 2015

[Modexp(2,n-1,n): n in [1..110]]; // G. C. Greubel, Jan 11 2023

Array[Mod[2^(# - 1), #] &, 105] (* Michael De Vlieger, Jul 01 2018 *)
Array[PowerMod[2,#-1,#]&,120] (* Harvey P. Dale, May 17 2023 *)

A062173(n) = if(1==n, 0, lift(Mod(2, n)^(n-1))); \\ Antti Karttunen, Jul 01 2018

[power_mod(2,n-1,n) for n in range(1,110)] # G. C. Greubel, Jan 11 2023

a(n) = A106262(2*n-3, n-2). - G. C. Greubel, Jan 11 2023

More terms from Antti Karttunen, Jul 01 2018

A050259 Numbers n such that 2^n == 3 (mod n).

Original entry on oeis.org

1, 4700063497, 3468371109448915, 8365386194032363, 10991007971508067

Offset: 1

Eric W. Weisstein

No other terms below 10^18. - Max Alekseyev, Oct 17 2017

Terms were computed: a(2) by the Lehmers, a(3) by Max Alekseyev, a(4) and a(5) by Joe K. Crump, a(?) = 63130707451134435989380140059866138830623361447484274774099906755 by P.-L. Montgomery.

R. Daniel Mauldin and S. M. Ulam, Mathematical problems and games. Adv. in Appl. Math. 8 (1987), pp. 281-344.

Joe K. Crump, 2^n mod n
R. K. Guy, The Strong Law of Small Numbers, Amer. Math. Monthly 95 (1988), pp. 697-712. See example 13.
R. K. Guy, The strong law of small numbers. Amer. Math. Monthly 95 (1988), no. 8, 697-712. [Annotated scanned copy]
Eric Weisstein's World of Mathematics, 2
OEIS Wiki, 2^n mod n

Cf. A001567, A036236, A015940, A015910.

m = 2; Join[Select[Range[m], Divisible[2^# - m, #] &],
Select[Range[m + 1, 10^6], PowerMod[2, #, #] == m &]] (* Robert Price, Oct 08 2018 *)

is(n)=Mod(2,n)^n==3 \\ Charles R Greathouse IV, Jun 11 2015

A015921 Positive integers n such that 2^n == 4 (mod n).

Original entry on oeis.org

1, 2, 4, 6, 10, 12, 14, 22, 26, 30, 34, 38, 46, 58, 62, 74, 82, 86, 94, 106, 118, 122, 132, 134, 142, 146, 158, 166, 170, 178, 182, 194, 202, 206, 214, 218, 226, 254, 262, 274, 278, 298, 302, 314, 326, 334, 346, 358, 362, 372, 382, 386, 394, 398, 422, 446

Offset: 1

Robert G. Wilson v

nonn

Odd terms are given by A173572.

For all m, 2^A050259(m)-1 belongs to this sequence.

T. D. Noe, Table of n, a(n) for n = 1..1000
OEIS Wiki, 2^n mod n

Contains A050990 as a subsequence.

Cf. A015910, A173572.

Select[Range[500], PowerMod[2, #, #] == 4 &] (* Alonso del Arte, Jul 07 2011 *)

Edited and terms 1,2,4 prepended by Max Alekseyev, Jul 29 2011

A033982 Integers n such that 2^n == 11 (mod n).

Original entry on oeis.org

1, 3, 262279, 143823239, 382114303, 1223853491, 381541784791, 556985326431, 6236258437049, 98828020264153

Offset: 1

Joe K. Crump (joecr(AT)carolina.rr.com)

894157816841269897394424491194255510200782699 belongs to this sequence. [From Max Alekseyev]

Joe K. Crump, 2^n mod n

Cf. A125000, A124974, A033983, A033981, A050259, A124977, A124965, A015911, A015910.

Cf. A015910, A015911, A033981, A050259, A124965, A124974, A124977, A015910, A015911, A033983, A125000.

m = 11; Join[Select[Range[m], Divisible[2^# - m, #] &],
Select[Range[m + 1, 10^3], PowerMod[2, #, #] == m &]] (* Robert Price, Oct 08 2018 *)

Edited by N. J. A. Sloane, Jul 03 2008 at the suggestion of R. J. Mathar
Terms 1, 3 prepended by Max Alekseyev, May 18 2011
a(9), a(10) from Max Alekseyev, Jul 30 2011

A066601 a(n) = 3^n mod n.

Original entry on oeis.org

0, 1, 0, 1, 3, 3, 3, 1, 0, 9, 3, 9, 3, 9, 12, 1, 3, 9, 3, 1, 6, 9, 3, 9, 18, 9, 0, 25, 3, 9, 3, 1, 27, 9, 12, 9, 3, 9, 27, 1, 3, 15, 3, 37, 18, 9, 3, 33, 31, 49, 27, 29, 3, 27, 12, 9, 27, 9, 3, 21, 3, 9, 27, 1, 48, 3, 3, 13, 27, 39, 3, 9, 3, 9, 57

Offset: 1

Amarnath Murthy, Dec 22 2001

			a(7) = 3 as 3^7 = 2187 = 7*312 + 3.

Harry J. Smith and Seiichi Manyama, Table of n, a(n) for n = 1..10000 (first 1000 terms from Harry J. Smith)

Cf. k^n mod n: A015910 (k=2), this sequence (k=3), A066602 (k=4), A066603 (k=5), A066604 (k=6), A066438 (k=7), A066439 (k=8), A066440 (k=9), A056969 (k=10), A066441 (k=11), A066442 (k=12), A116609 (k=13).

seq(irem(3^n,n),n=1..75); # Zerinvary Lajos, Apr 20 2008

Mathematica
```
Table[PowerMod[3, n, n], {n, 75}]
```

a(n) = { lift(Mod(3, n)^n) } \\ Harry J. Smith, Mar 09 2010

def A066601(n): return pow(3,n,n) # Chai Wah Wu, Aug 24 2023

More terms from Robert G. Wilson v, Dec 27 2001

A090305 a(n) = 16*a(n-1) + a(n-2), starting with a(0) = 2 and a(1) = 16.

Original entry on oeis.org

2, 16, 258, 4144, 66562, 1069136, 17172738, 275832944, 4430499842, 71163830416, 1143051786498, 18359992414384, 294902930416642, 4736806879080656, 76083812995707138, 1222077814810394864, 19629328849962024962

Offset: 0

Nikolay V. Kosinov (kosinov(AT)unitron.com.ua), Jan 25 2004

Lim_{n-> infinity} a(n)/a(n+1) = 0.0622577... = 1/(8+sqrt(65)) = (sqrt(65)-8).

Lim_{n-> infinity} a(n+1)/a(n) = 16.0622577... = (8+sqrt(65)) = 1/(sqrt(65)-8).

			a(4) = 16*a(3) + a(2) = 16*4144 + 258 = (8+sqrt(65))^4 + (8-sqrt(65))^4 = 66561.99998497... + 0.00001502... = 66562.

G. C. Greubel, Table of n, a(n) for n = 0..500
Tanya Khovanova, Recursive Sequences
Index entries for recurrences a(n) = k*a(n - 1) +/- a(n - 2)
Index entries for linear recurrences with constant coefficients, signature (16,1).

Cf. A002070, A015910.
Lucas polynomials: A114525.
Lucas polynomials Lucas(n,m): A000032 (m=1), A002203 (m=2), A006497 (m=3), A014448 (m=4), A087130 (m=5), A085447 (m=6), A086902 (m=7), A086594 (m=8), A087798 (m=9), A086927 (m=10), A001946 (m=11), A086928 (m=12), A088316 (m=13), A090300 (m=14), A090301 (m=15), this sequence (m=16), A090306 (m=17), A090307 (m=18), A090308 (m=19), A090309 (m=20), A090310 (m=21), A090313 (m=22), A090314 (m=23), A090316 (m=24), A330767 (m=25), A087281 (m=29), A087287 (m=76), A089772 (m=199).

m:=16;; a:=[2,m];; for n in [3..20] do a[n]:=m*a[n-1]+a[n-2]; od; a; # G. C. Greubel, Dec 31 2019

m:=16; I:=[2,m]; [n le 2 select I[n] else m*Self(n-1) +Self(n-2): n in [1..20]]; // G. C. Greubel, Dec 31 2019

seq(simplify(2*(-I)^n*ChebyshevT(n, 8*I)), n = 0..20); # G. C. Greubel, Dec 31 2019

LinearRecurrence[{16,1},{2,16},40] (* or *) With[{c=Sqrt[65]}, Simplify/@ Table[(c-8)((8+c)^n-(8-c)^n (129+16c)),{n,20}]] (* Harvey P. Dale, Oct 31 2011 *)
LucasL[Range[20]-1, 16] (* G. C. Greubel, Dec 31 2019 *)

vector(21, n, 2*(-I)^(n-1)*polchebyshev(n-1, 1, 8*I) ) \\ G. C. Greubel, Dec 31 2019

[2*(-I)^n*chebyshev_T(n, 8*I) for n in (0..20)] # G. C. Greubel, Dec 31 2019

a(n) = 16*a(n-1) + a(n-2), starting with a(0) = 2 and a(1) = 16.
a(n) = (8+sqrt(65))^n + (8-sqrt(65))^n.
a(n)^2 = a(2n) - 2 if n = 1, 3, 5, ...;
a(n)^2 = a(2n) + 2 if n = 2, 4, 6, ....
G.f.: (2-16*x)/(1-16*x-x^2). - Philippe Deléham, Nov 02 2008
a(n) = Lucas(n, 16) = 2*(-i)^n * ChebyshevT(n, 8*i). - G. C. Greubel, Dec 31 2019
E.g.f.: 2*exp(8*x)*cosh(sqrt(65)*x). - Stefano Spezia, Jan 01 2020

More terms from Ray Chandler, Feb 14 2004

A015911 Numbers k such that 2^k mod k is odd.

Original entry on oeis.org

25, 45, 55, 91, 95, 99, 125, 135, 143, 153, 155, 161, 175, 187, 225, 235, 245, 247, 261, 273, 275, 279, 285, 289, 297, 319, 329, 333, 335, 355, 363, 369, 387, 391, 403, 407, 413, 423, 425, 429, 435, 437, 441, 459, 473, 477, 481, 483, 493, 507, 517, 525, 529

Offset: 1

Robert G. Wilson v

nonn

All terms are composite: due to Fermat's little theorem, 2^p == 2 (mod p) when p is prime. - M. F. Hasler, May 10 2021

Zak Seidov, Table of n, a(n) for n = 1..10000
Wikipedia, Fermat's little theorem.

Cf. A015910, A226221.

q:= n-> is(2&^n mod n, odd):
select(q, [$1..1000])[];  # Alois P. Heinz, May 10 2021

Select[Range@532, OddQ@PowerMod[2, #, # ] &]

is(n)=lift(Mod(2,n)^n)%2 \\ Charles R Greathouse IV, May 31 2013

cp's OEIS Frontend

A036236 Least inverse of A015910: smallest integer k > 0 such that 2^k mod k = n, or 0 if no such k exists.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A372707 Smallest natural number requiring n applications of the map x -> 2^x mod x = A015910(x) to reach 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

C

Python

Extensions

A180075 If A015910(m) is a power of 2, append log_2(A015910(m)) to the sequence.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula

A062173 a(n) = 2^(n-1) mod n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

PARI

SageMath

Formula

Extensions

A050259 Numbers n such that 2^n == 3 (mod n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

A015921 Positive integers n such that 2^n == 4 (mod n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A033982 Integers n such that 2^n == 11 (mod n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica