A062173 -id:A062173 - cp's OEIS frontend

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

0, 0, 2, 0, 2, 4, 2, 0, 8, 4, 2, 4, 2, 4, 8, 0, 2, 10, 2, 16, 8, 4, 2, 16, 7, 4, 26, 16, 2, 4, 2, 0, 8, 4, 18, 28, 2, 4, 8, 16, 2, 22, 2, 16, 17, 4, 2, 16, 30, 24, 8, 16, 2, 28, 43, 32, 8, 4, 2, 16, 2, 4, 8, 0, 32, 64, 2, 16, 8, 44, 2, 64, 2, 4, 68, 16, 18, 64, 2, 16, 80, 4, 2, 64

Offset: 1

Robert G. Wilson v

nonn

2^n == 2 mod n if and only if n is a prime or a member of A001567 or of A006935. [Guy]. - N. J. A. Sloane, Mar 22 2012; corrected by Thomas Ordowski, Mar 26 2016
Known solutions to 2^n == 3 (mod n) are given in A050259.
This sequence is conjectured to include every integer k >= 0 except k = 1. A036236 includes a proof that k = 1 is not in this sequence, and n = A036236(k) solves a(n) = k for all other 0 <= k <= 1000. - David W. Wilson, Oct 11 2011
It could be argued that a(0) := 1 would make sense, e.g., thinking of "mod n" as "in Z/nZ", and/or because (anything)^0 = 1. See also A112987. - M. F. Hasler, Nov 09 2018

			a(7) = 2 because 2^7 = 128 = 2 mod 7.
a(8) = 0 because 2^8 = 256 = 0 mod 8.
a(9) = 8 because 2^9 = 512 = 8 mod 9.

Richard K. Guy, Unsolved Problems in Number Theory, F10.

T. D. Noe, Table of n, a(n) for n=1..10000
Albert Frank, International Contest Of Logical Sequences, 2002 - 2003. Item 4
Albert Frank, Solutions of International Contest Of Logical Sequences, 2002 - 2003.
Peter L. Montgomery, 65-digit solution.

Cf. A036236, A015911, A015921, A001567.

Cf. A000079, A062173, A082495.

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

[Modexp(2, n, n): n in [1..100]]; // Vincenzo Librandi, Nov 09 2018

A015910 := n-> modp(2 &^ n,n) ; # Zerinvary Lajos, Feb 15 2008

Mathematica
```
Table[PowerMod[2, n, n], {n, 85}]
```

makelist(power_mod(2, n, n), n, 1, 84); /* Bruno Berselli, May 20 2011 */

a(n)=lift(Mod(2,n)^n) \\ Charles R Greathouse IV, Jul 15 2011

a(2^k) = 0. - Alonso del Arte, Nov 10 2014

a(n) == 2^(n-phi(n)) mod n, where phi(n) = A000010(n). - Thomas Ordowski, Mar 26 2016

A176997 Integers k such that 2^(k-1) == 1 (mod k).

Original entry on oeis.org

1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331

Offset: 1

Juri-Stepan Gerasimov, Dec 08 2010

nonn

Old definition was: Odd integers n such that 2^(n-1) == 4^(n-1) == 8^(n-1) == ... == k^(n-1) (mod n), where k = A062383(n). Dividing 2^(n-1) == 4^(n-1) (mod n) by 2^(n-1), we get 1 == 2^(n-1) (mod n), implying the current definition. - Max Alekseyev, Sep 22 2016
The union of {1}, the odd primes, and the Fermat pseudoprimes, i.e., {1} U A065091 U A001567. Also, the union of A006005 and A001567 (conjectured by Alois P. Heinz, Dec 10 2010). - Max Alekseyev, Sep 22 2016
These numbers were called "fermatians" by Shanks (1962). - Amiram Eldar, Apr 21 2024

			5 is in the sequence because 2^(5-1) == 4^(5-1) == 8^(5-1) == 1 (mod 5).

Daniel Shanks, Solved and Unsolved Problems in Number Theory, Spartan Books, Washington D.C., 1962.

Seiichi Manyama, Table of n, a(n) for n = 1..10000

The odd terms of A015919.
Odd integers n such that 2^n == 2^k (mod n): this sequence (k=1), A173572 (k=2), A276967 (k=3), A033984 (k=4), A276968 (k=5), A215610 (k=6), A276969 (k=7), A215611 (k=8), A276970 (k=9), A215612 (k=10), A276971 (k=11), A215613 (k=12).
Cf. A000079, A062173, A062175, A176817.

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

isok(n) = Mod(2, n)^(n-1) == 1; \\ Michel Marcus, Sep 23 2016

from itertools import count, islice
def A176997_gen(startvalue=1): # generator of terms >= startvalue
    if startvalue <= 1:
        yield 1
    k = 1<<(s:=max(startvalue,1))-1
    for n in count(s):
        if k % n == 1:
            yield n
        k <<= 1
A176997_list = list(islice(A176997_gen(),30)) # Chai Wah Wu, Jun 30 2022

Edited by Max Alekseyev, Sep 22 2016

A174275 a(n) = 2^(n-1) mod M(n) where M(n) = A014963(n) is the exponential of the Mangoldt function.

Original entry on oeis.org

0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0

Offset: 1

Mats Granvik, Mar 14 2010

Appears to be always either 0 or 1.
This follows from Fermat's Little Theorem. - Charles R Greathouse IV, Feb 13 2011
Characteristic function for odd prime powers (larger than one). - Antti Karttunen, Sep 14 2017, after Charles R Greathouse IV's Feb 13 2011 formula.

Antti Karttunen, Table of n, a(n) for n = 1..16385
Index entries for characteristic functions

Cf. A062173.

a[n_] := Mod[2^(n - 1), Exp[MangoldtLambda[n]]] (* Steven Foster Clark, Sep 04 2023 *)

vector(70, n, ispower(k=n, , &k); isprime(k)&k!=2) \\ Charles R Greathouse IV, Feb 13 2011

a(n) = A000079(n-1) mod A014963(n).

a(n) = 1 if n = p^k for k > 0 and p a prime not equal to 2, a(n) = 0 otherwise. - Charles R Greathouse IV, Feb 13 2011

More terms from Antti Karttunen, Sep 14 2017

Name corrected by Steven Foster Clark, Sep 05 2023

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

Original entry on oeis.org

0, 1, 1, 3, 1, 3, 1, 7, 7, 3, 1, 3, 1, 3, 7, 15, 1, 9, 1, 15, 7, 3, 1, 15, 6, 3, 25, 15, 1, 3, 1, 31, 7, 3, 17, 27, 1, 3, 7, 15, 1, 21, 1, 15, 16, 3, 1, 15, 29, 23, 7, 15, 1, 27, 42, 31, 7, 3, 1, 15, 1, 3, 7, 63, 31, 63, 1, 15, 7, 43, 1, 63, 1, 3, 67, 15, 17, 63, 1, 15, 79, 3, 1, 63, 31, 3, 7, 79

Offset: 1

Anonymous, Apr 28 2003

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A015910, A048298.

Cf. A000079, A062173.

a082495 n = a015910 n + a048298 n - 1  -- Reinhard Zumkeller, Oct 17 2015

Table[Mod[2^m-1,m],{m,6!}] (* Vladimir Joseph Stephan Orlovsky, Feb 11 2010 *)

vector(80, n, (2^n-1) %n) \\ Michel Marcus, Jan 16 2015

def A082495(n): return (m if (m:=pow(2,n,n)) else n)-1 # Chai Wah Wu, Dec 01 2022

a(n) = A015910(n) + A048298(n) - 1.

A106262 An invertible triangle of remainders of 2^n.

Original entry on oeis.org

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

Offset: 0

Paul Barry, Apr 28 2005

			Triangle begins:
  1;
  0, 1;
  0, 2, 1;
  0, 1, 2, 1;
  0, 2, 0, 2, 1;
  0, 1, 0, 4, 2, 1;
  0, 2, 0, 3, 4, 2, 1;
  0, 1, 0, 1, 2, 4, 2, 1;
  0, 2, 0, 2, 4, 1, 4, 2, 1;
  0, 1, 0, 4, 2, 2, 0, 4, 2, 1;

G. C. Greubel, Rows n = 0..50 of the triangle, flattened

Cf. A106263 (row sums), A106264 (diagonal sums).

Cf. A000034, A015910, A062173, A112983, A213859, A294389, A294390.

[Modexp(2, n-k, k+2): k in [0..n], n in [0..15]]; // G. C. Greubel, Jan 10 2023

Table[PowerMod[2, n-k, k+2], {n,0,15}, {k,0,n}]//Flatten (* G. C. Greubel, Jan 10 2023 *)

flatten([[power_mod(2,n-k,k+2) for k in range(n+1)] for n in range(16)]) # G. C. Greubel, Jan 10 2023

T(n, k) = 2^(n-k) mod (k+2).
Sum_{k=0..n} T(n, k) = A106263(n) (row sums).
Sum_{k=0..floor(n/2)} T(n-k, k) = A106264(n) (diagonal sums).
From G. C. Greubel, Jan 10 2023: (Start)
T(n, 0) = A000007(n).
T(n, 1) = A000034(n+1).
T(2*n, n) = A213859(n).
T(2*n, n-1) = A015910(n+1).
T(2*n, n+1) = A294390(n+3).
T(2*n+1, n-1) = A112983(n+1).
T(2*n+1, n+1) = A294389(n+3).
T(2*n-1, n-1) = A062173(n+1). (End)

A213859 a(n) = 2^n mod (n+2).

Original entry on oeis.org

1, 2, 0, 3, 4, 4, 0, 2, 6, 6, 4, 7, 8, 2, 0, 9, 16, 10, 4, 2, 12, 12, 16, 8, 14, 20, 4, 15, 16, 16, 0, 2, 18, 22, 16, 19, 20, 2, 24, 21, 16, 22, 4, 38, 24, 24, 16, 32, 6, 2, 4, 27, 34, 52, 8, 2, 30, 30, 4, 31, 32, 2, 0, 8, 16, 34, 4, 2, 46, 36, 16, 37, 38, 17

Offset: 0

Alex Ratushnyak, Jun 22 2012

Conjectures:
Indices of zeros: 2^(x+2)-2, x >= 0.
There are infinitely many n's such that a(n)=n.
Every integer k >= 0 appears in a(n) at least once.
Every k >= 0 appears in a(n) infinitely many times.

G. C. Greubel, Table of n, a(n) for n = 0..10000

Cf. A015910, A066606, A062173, A106262.

[Modexp(2,n,n+2): n in [0..120]]; // G. C. Greubel, Jan 11 2023

Table[PowerMod[2, n, n+2], {n, 0, 100}] (* T. D. Noe, Jun 26 2012 *)

print([2**n % (n+2) for n in range(222)])

[power_mod(2,n,n+2) for n in range(121)] # G. C. Greubel, Jan 11 2023

a(n) = 2^n mod (n+2).

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

A062172 Table T(n,k) by antidiagonals of n^(k-1) mod k [n,k > 0].

Original entry on oeis.org

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

Offset: 1

Henry Bottomley, Jun 12 2001

			T(5,3)=5^(3-1) mod 3=25 mod 3=1. Rows start (0,1,1,1,1,...), (0,0,1,0,1,...), (0,1,0,3,1...), (0,0,1,0,1,...), (0,1,1,1,0,...), ...

Cf. A002997, A060154. Rows include A057427, A062173, A062174, A062175, A062176. Columns include A000004, A000035, A011655, A010684 with interleaved 0's, A011558, A010875. Diagonals include all the rows again and A000004 and A009001 unsigned.

A073797 a(n) = 2^n mod pi(n).

Original entry on oeis.org

0, 0, 0, 2, 1, 0, 0, 0, 0, 3, 1, 2, 4, 2, 4, 4, 1, 0, 0, 0, 0, 5, 1, 2, 4, 8, 7, 2, 4, 2, 4, 8, 5, 10, 9, 8, 4, 8, 4, 6, 12, 2, 4, 8, 2, 8, 1, 2, 4, 8, 1, 0, 0, 0, 0, 0, 0, 8, 16, 2, 4, 8, 16, 14, 10, 3, 6, 12, 5, 8, 16, 2, 4, 8, 16, 11, 1, 6, 12, 2, 4, 18, 13, 3, 6, 12, 1, 8, 16, 8, 16, 8, 16, 8, 16

Offset: 2

Labos Elemer, Aug 12 2002

nonn

			From _Michael De Vlieger_, Dec 09 2018: (Start)
a(2) = 0 since 2^2 mod PrimePi(2) = 4 mod 1 = 0.
a(5) = 2 since 2^5 mod PrimePi(5) = 32 mod 3 = 2. (End)

Michael De Vlieger, Table of n, a(n) for n = 2..10000

Cf. A000079, A000720, A015910, A062173, A064367.

[2^n mod #PrimesUpTo(n): n in [2..100]]; // G. C. Greubel, Dec 10 2018

Array[Mod[2^#, PrimePi@ #] &, 95, 2] (* Michael De Vlieger, Dec 09 2018 *)
Table[PowerMod[2,n,PrimePi[n]],{n,2,100}] (* Harvey P. Dale, Aug 30 2021 *)

for(n=2, 100, print1(lift(Mod(2^n, primepi(n))), ", ")) \\ G. C. Greubel, Dec 10 2018

[mod(2^n, prime_pi(n)) for n in (2..100)] # G. C. Greubel, Dec 10 2018

a(n) = A000079(n) mod A000720(n).

A110146 a(n) = n^(n+1) mod (n+2).

Original entry on oeis.org

0, 1, 0, 1, 4, 1, 0, 4, 8, 1, 4, 1, 12, 4, 0, 1, 4, 1, 12, 4, 20, 1, 16, 16, 24, 13, 20, 1, 28, 1, 0, 4, 32, 9, 4, 1, 36, 4, 32, 1, 10, 1, 36, 31, 44, 1, 16, 15, 38, 4, 44, 1, 40, 49, 40, 4, 56, 1, 52, 1, 60, 4, 0, 16, 34, 1, 60, 4, 48, 1, 40, 1, 72, 34, 68, 9

Offset: 0

Zak Seidov, Jul 14 2005

nonn

First occurrence of n such that n^(n+1) (mod n+2) == k for k = 1, 2, 3, ..., or 0 if no such n is known: 1, 20735, 10667, 4, 0, 3761, 3820819, 8, 33, 40, 350849481, 12, 25, ..., .

Congruences not yet occurring for n < 4.6*10^9: 5, 47, 57, 105, 203, 233, 255, 293, 333, 354, 377, 405, 433, ..., .

Carl R. White, Table of n, a(n) for n = 0..10000

Cf. A000918, A040976.

Table[PowerMod[n, n+1, n+2], {n, 0, 120}]

a(n) = lift(Mod(n, n+2)^(n+1)); \\ Michel Marcus, Dec 17 2022

a(A000918(n)) = 0 for n >= 1, a(A040976(n)) = 1 for n >= 2.

a(n-2) = A062173(n) if n is odd or n is power of two, and a(n-2) = n - A062173(n) otherwise. - Thomas Ordowski, Nov 28 2013

A212844 a(n) = 2^(n+2) mod n.

Original entry on oeis.org

0, 0, 2, 0, 3, 4, 1, 0, 5, 6, 8, 4, 8, 2, 2, 0, 8, 4, 8, 4, 11, 16, 8, 16, 3, 16, 23, 8, 8, 16, 8, 0, 32, 16, 2, 4, 8, 16, 32, 24, 8, 4, 8, 20, 23, 16, 8, 16, 22, 46, 32, 12, 8, 4, 7, 16, 32, 16, 8, 4, 8, 16, 32, 0, 63, 58, 8, 64, 32, 36, 8, 40, 8, 16, 47

Offset: 1

Alex Ratushnyak, Jul 22 2012

nonn

Also a(n) = x^x mod (x-2), where x = n+2.
Indices of 0's: 2^k, k>=0.
Indices of 1's: 7, 511, 713, 11023, 15553, 43873, 81079, 95263, 323593, 628153, 2275183, 6520633, 6955513, 7947583, 10817233, 12627943, 14223823, 15346303, 19852423, 27923663, 28529473, ...
Conjecture: every integer k >= 0 appears in a(n) at least once.
Each number below 69 appears at least once. Some large first occurrences: a(39806401) = 25, a(259274569) = 33, a(10571927) = 55, a(18039353) = 81. - Charles R Greathouse IV, Jul 21 2015

			a(3) = 2^5 mod 3 = 32 mod 3 = 2.

Harvey P. Dale, Table of n, a(n) for n = 1..1000

Cf. A000312, A015910, A062173, A112983, A213381, A213859.

A212844 := proc(n)
    modp( 2&^ (n+2),n) ;
end proc: # R. J. Mathar, Jul 24 2012

Table[PowerMod[2, n+2, n], {n, 79}] (* Alonso del Arte, Jul 22 2012 *)

A212844(n)=lift(Mod(2,n)^(n+2)) \\ M. F. Hasler, Jul 23 2012

for n in range(1,99):
    print(2**(n+2) % n, end=',')

a(n) = 2^(n+2) mod n.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

Maxima

PARI

Formula

A176997 Integers k such that 2^(k-1) == 1 (mod k).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

Extensions

A174275 a(n) = 2^(n-1) mod M(n) where M(n) = A014963(n) is the exponential of the Mangoldt function.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Formula

A106262 An invertible triangle of remainders of 2^n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A213859 a(n) = 2^n mod (n+2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Python

SageMath