A007733 -id:A007733 - cp's OEIS frontend

A037178 Longest cycle when squaring modulo n-th prime.

1, 1, 1, 2, 4, 2, 1, 6, 10, 3, 4, 6, 4, 6, 11, 12, 28, 4, 10, 12, 6, 12, 20, 10, 2, 20, 8, 52, 18, 3, 6, 12, 8, 22, 36, 20, 12, 54, 82, 14, 11, 12, 36, 2, 21, 30, 12, 36, 28, 18, 28, 24, 4, 100, 1, 130, 66, 36, 22, 12, 46, 9, 24, 20, 12, 39, 20, 6, 172, 28, 10, 178, 60, 10, 18

Offset: 1

Jud McCranie

nonn

a(n)=1 for Fermat primes, A019434. a(n)=2 for primes in A039687. a(n)=3 for primes in A050527. Sequence A141305 gives those primes p > 3 having the longest possible cycle, (p-3)/2. - T. D. Noe, Jun 24 2008

T. D. Noe, Table of n, a(n) for n=1..10000
E. L. Blanton, Jr., S. P. Hurd and J. S. McCranie, On a digraph defined by squaring modulo n, Fibonacci Quart. 30 (Nov. 1992), 322-333.
Haifeng Xu, The largest cycles consist by the quadratic residues and Fermat primes, arXiv:1601.06509 [math.NT], 2016. See table on page 2.

Cf. A002322, A007733, A256608.
Cf. A019434, A039687, A050527, A141305.
Cf. A037179, A037180.
a(n) = maximal entry in row p of A278185.

a[n_] := Module[{p = Prime[n], k}, k = (p-1)/2^IntegerExponent[p-1, 2]; MultiplicativeOrder[2, k]]; Array[a, 100] (* Jean-François Alcover, Jan 28 2016, after T. D. Noe *)

a(n) = {ppn = prime(n) - 1; k = ppn >> valuation(ppn, 2); znorder(Mod(2, k));} \\ Michel Marcus, Nov 11 2015

rpsi(n) = lcm(znstar(n)[2]); \\ A002322
pb(n) = znorder(Mod(2, n/2^valuation(n, 2))); \\ A007733
a(n) = pb(rpsi(prime(n))); \\ Michel Marcus, Jan 28 2016

Let p=prime(n) and k=A000265(p-1), the odd part of p-1. Then a(n) = ord(2,k), that is, the smallest positive integer x such that 2^x = 1 (mod k). - T. D. Noe, Jun 24 2008
a(n) = A007733(A002322(prime(n))). - Michel Marcus, Jan 28 2016
a(n) = A256608(prime(n)).

A256608 Longest eventual period of a^(2^k) mod n for all a.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 4, 1, 2, 2, 1, 1, 1, 2, 6, 1, 2, 4, 10, 1, 4, 2, 6, 2, 3, 1, 4, 1, 4, 1, 2, 2, 6, 6, 2, 1, 4, 2, 6, 4, 2, 10, 11, 1, 6, 4, 1, 2, 12, 6, 4, 2, 6, 3, 28, 1, 4, 4, 2, 1, 2, 4, 10, 1, 10, 2, 12, 2, 6, 6, 4, 6, 4, 2, 12, 1, 18, 4, 20, 2, 1, 6

Offset: 1

Ivan Neretin, Apr 04 2015

nonn

a(n) is a divisor of phi(phi(n)) (A010554).

			In other words, eventual period of {0..n-1} under the map x -> x^2 mod n.
For example, with n=10 the said map acts as follows. Read down the columns: the column headed 2 for example means that (repeatedly squaring mod 10), 2 goes to 4 goes to 16 = 6 (mod 10) goes to 36 = 6 mod 10 --- and has reached a fixed point.
0 1 2 3 4 5 6 7 8 9
0 1 4 9 6 5 6 9 4 1
0 1 6 1 6 5 6 1 6 1
0 1 6 1 6 5 6 1 6 1
and thus every number reaches a fixed point. This means the eventual common period is 1, hence a(10)=1.

Ivan Neretin, Table of n, a(n) for n = 1..10000
Haifeng Xu, The largest cycles consist by the quadratic residues and Fermat primes, arXiv:1601.06509 [math.NT], 2016.

Cf. A001146, A002322, A002326, A007733, A010554, A037178.
First differs from A256607 at n=43.
LCM of entries in row n of A279185.

a[n_] := With[{lambda = CarmichaelLambda[n]}, MultiplicativeOrder[2, lambda / (2^IntegerExponent[lambda, 2])]]; Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Jan 28 2016 *)

rpsi(n) = lcm(znstar(n)[2]); \\ A002322
pb(n) = znorder(Mod(2, n/2^valuation(n, 2))); \\ A007733
a(n) = pb(rpsi(n)); \\ Michel Marcus, Jan 28 2016

a(n) = A007733(A002322(n)).

a(prime(n)) = A037178(n). - Michel Marcus, Jan 27 2016

Name changed by Jianing Song, Feb 02 2025

A295740 Even pseudoprimes (A006935) that are not squarefree.

Original entry on oeis.org

190213279479817426, 283959621257123566, 301971651496560046, 575203724324614126, 800951203404568126, 849341919686285026, 1118572636403947726, 2080713636347910526, 2270517620327541586, 2767984602684877486, 5013069719001987826, 5133266340887464066, 5252931629341901506, 5743747078662858526

Offset: 1

Max Alekseyev, Nov 26 2017

nonn

For a prime p, if p^2 divides an even pseudoprime, then p is a Wieferich prime (A001220) and A007733(p)=A002326((p-1)/2) is odd. Currently, the only known such prime is p=3511.

So, all known terms are multiples of 3511^2. Furthermore, no term can be a multiple of 3511^3.

			a(1) = 190213279479817426 = 2 * 7 * 79 * 1951 * 3511^2 * 7151.
a(2) = 283959621257123566 = 2 * 599 * 937 * 3511^2 * 20521.
a(3) = 301971651496560046 = 2 * 31 * 71 * 73 * 3511^2 * 76231.

Max Alekseyev, Table of n, a(n) for n = 1..80 (5 wrong terms were removed by _Mauro Fiorentini_, May 31 2020)

Intersection of A006935 and A013929.

The even terms of A158358. Also, unless there is a Wieferich prime greater than 3511, the even terms of A247831.

A292544 Numbers h such that 2^phi(h) == phi(h) (mod h).

Original entry on oeis.org

1, 12, 40, 48, 60, 192, 544, 640, 680, 704, 768, 816, 960, 1020, 1664, 3072, 10240, 11008, 12288, 13760, 15360, 19456, 24320, 49152, 83968, 125952, 131584, 139264, 139808, 163840, 164480, 174080, 174760, 196608, 197376, 208896, 209712, 245760, 246720, 261120, 262140, 720896, 786432

Offset: 1

Max Alekseyev and Altug Alkan, Sep 18 2017

Conjecture: For n > 1, a(n) is a Zumkeller number (A083207) [confirmed for n up to 47]. - Ivan N. Ianakiev, Sep 22 2017

			704 = 11*2^6 is a term since phi(11*2^6) = 5*2^6 and 11*2^6 divides 2^(5*2^6) - 5*2^6.

Giovanni Resta, Table of n, a(n) for n = 1..180 (terms < 10^12; first 101 terms from Michel Marcus)

Cf. A000010, A007733, A066781.

{1}~Join~Select[Range[10^6], Function[n, # == PowerMod[2, #, n] &@ EulerPhi@ n]] (* Michael De Vlieger, Sep 18 2017 *)

isok(n) = Mod(2, n)^eulerphi(n)==eulerphi(n);

Let m be an odd number, z = A007733(m) and k, 0 <= k < z, be such that phi(m) == 2^k (mod m); then m*2^(i*z - k + 1) belongs to this sequence for all i >= 1. And this is a general form of the terms of this sequence.
Some families of solutions of the form m*2^(i*z - k + 1):
If m = 3, then z = 2 and k = 1 ==> 3*2^(2*i) is a term for all i >= 1.
If m = 5, then z = 4 and k = 2 ==> 5*2^(4*i-1) is a term for all i >= 1.
If m = 7, then z = 3 but k does not exist ==> no term with odd part equal to 7.
If m = 15, then z = 4 and k = 3 ==> 15*2^(4*i-2) is a term for all i >= 1.
If m = 77, then z = 30 and k = 14 ==> 77*2^(30*i-13) is a term for all i >= 1.

A306231 Lexicographically earliest sequence of distinct positive terms such that for any n > 0 and any k > 0, floor((2^k) / a(n)) AND floor((2^k) / a(n+1)) = 0 (where AND denotes the bitwise AND operator).

Original entry on oeis.org

1, 2, 3, 6, 4, 5, 20, 8, 9, 72, 16, 7, 14, 21, 78, 32, 11, 352, 64, 10, 40, 15, 24, 12, 30, 35, 390, 48, 96, 51, 102, 60, 13, 832, 117, 144, 18, 168, 42, 28, 39, 180, 56, 84, 63, 70, 780, 120, 26, 128, 19, 504, 36, 288, 126, 45, 112, 151, 896, 156, 720, 224

Offset: 1

Rémy Sigrist, Jan 30 2019

In other words, for any n > 0, the binary expansions of 1/a(n) and of 1/a(n+1) have no common one bit; in this sense, this sequence is similar to A109812.

This sequence is a permutation of the natural numbers, with inverse A306233 (we can first prove that all the powers of 2 appear in the sequence and then that every natural number appear in the sequence).

			The first terms, alongside A007733(a(n)) and the binary representation of 1/a(n) with periodic part in parentheses, are:
  n   a(n)  period  bin(1/a(n))
  --  ----  ------  -------------------
   1     1       1  1.(0)
   2     2       1  0.1(0)
   3     3       2  0.(01)
   4     6       2  0.0(01)
   5     4       1  0.01(0)
   6     5       4  0.(0011)
   7    20       4  0.00(0011)
   8     8       1  0.001(0)
   9     9       6  0.(000111)
  10    72       6  0.000(000111)
  11    16       1  0.0001(0)
  12     7       3  0.(001)
  13    14       3  0.0(001)
  14    21       6  0.(000011)
  15    78      12  0.0(000001101001)
  16    32       1  0.00001(0)
  17    11      10  0.(0001011101)
  18   352      10  0.00000(0001011101)
  19    64       1  0.000001(0)
  20    10       4  0.0(0011)

Rémy Sigrist, Table of n, a(n) for n = 1..2000
Rémy Sigrist, PARI program for A306231
Index entries for sequences that are permutations of the natural numbers

Cf. A000120, A007733, A109812, A306233 (inverse).

PARI
```
See Links section.
```

For any n > 0, if A000120(a(n)) <> 1 and A000120(a(n+1)) <> 1, then gcd(A007733(a(n)), A007733(a(n+1))) > 1.

A382173 a(n) is the sum of row n of A382172.

Original entry on oeis.org

0, 1, 2, 1, 6, 7, 4, 2, 6, 16, 1, 5, 8, 14, 10, 5, 10, 6, 3, 15, 2, 7, 13, 4, 26, 24, 19, 9, 1, 31, 6, 10, 8, 10, 20, 4, 22, 2, 13, 14, 11, 11, 24, 5, 31, 13, 8, 4, 30, 80, 17, 20, 30, 18, 2, 11, 17, 9, 14, 30, 16, 5, 10, 25, 36, 29, 38, 6, 9, 63, 16, 2, 40, 64

Offset: 1

Amiram Eldar, Mar 17 2025

The sum of digits (or, equivalently, the number of 1's) of the period of 1/n when expanded in golden ratio base.

			The first 5 terms and the corresponding rows of A382172 are:
  n | a(n) | row n
 ---+------+-----------------------------------------------------------
  1 |    0 | 0
  2 |    1 | 0, 1, 0
  3 |    2 | 0, 0, 1, 0, 1, 0, 0, 0
  4 |    1 | 0, 0, 1, 0, 0, 0
  5 |    6 | 0, 0, 0 ,1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000032, A002878, A007733, A055778, A093960, A276350, A382172, A382174, A382175, A382176.

a[n_] := Total[RealDigits[1/n, GoldenRatio, A001175[n], -1][[1]]]; Array[a, 100] (* using A001175[n] from A001175 *)

A296243 Numbers k such that the multiplicative order of 2 modulo k is even.

Original entry on oeis.org

3, 5, 9, 11, 13, 15, 17, 19, 21, 25, 27, 29, 33, 35, 37, 39, 41, 43, 45, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 75, 77, 81, 83, 85, 87, 91, 93, 95, 97, 99, 101, 105, 107, 109, 111, 113, 115, 117, 119, 121, 123, 125, 129, 131, 133, 135, 137, 139, 141, 143, 145, 147, 149, 153

Offset: 1

Max Alekseyev, Dec 09 2017

nonn

Odd numbers k such that A007733(k) = A002326((k-1)/2) is even.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Set difference of A005408 and A036259.
Contains A296244 as a subsequence.
The prime terms are given by A014662.
Cf. A002326, A007733.

A036259 = Select[Range[1, 199, 2], OddQ[MultiplicativeOrder[2, #]] &];
Range[1, A036259[[-1]], 2] ~Complement~ A036259 (* Jean-François Alcover, Dec 20 2017 *)
Select[Range[1, 153, 2], EvenQ[MultiplicativeOrder[2, #]] &] (* Amiram Eldar, Jul 30 2020 *)

{ is_A296243(n) = (n%2) && !(znorder(Mod(2,n))%2); }

A336503 2-practical numbers: numbers m such that the polynomial x^m - 1 has a divisor of every degree <= m in the prime field F_2[x].

Original entry on oeis.org

1, 2, 3, 4, 6, 8, 12, 14, 15, 16, 18, 20, 21, 24, 28, 30, 32, 36, 40, 42, 45, 48, 54, 56, 60, 63, 64, 70, 72, 80, 84, 90, 96, 100, 105, 108, 112, 120, 124, 126, 128, 132, 135, 136, 140, 144, 147, 150, 154, 156, 160, 162, 165, 168, 176, 180, 182, 186, 189, 192

Offset: 1

Amiram Eldar, Jul 23 2020

nonn

For a rational prime number p, a "p-practical number" is a number m such that the polynomial x^m - 1 has a divisor of every degree <= m in F_p[x], the prime field of order p.
A number m is 2-practical if and only if every number 1 <= k <= m can be written as Sum_{d|m} A007733(d) * n_d, where A007733(d) is the multiplicative order of 2 modulo the odd part of d, and 0 <= n_d <= phi(d)/A007733(d).
The number of terms not exceeding 10^k for k = 1, 2, ... are 6, 34, 243, 1790, 14703, 120276, 1030279, ...

Amiram Eldar, Table of n, a(n) for n = 1..10000
Paul Pollack and Lola Thompson, On the degrees of divisors of T^n-1>, New York Journal of Mathematics, Vo. 19 (2013), pp. 91-116, preprint, arXiv:1206.2084 [math.NT], 2012.
Lola Thompson, Products of distinct cyclotomic polynomials, Ph.D. thesis, Dartmouth College, 2012.
Lola Thompson, On the divisors of x^n - 1 in F_p[x], International Journal of Number Theory, Vol. 9, No. 2 (2013), pp. 421-430.
Lola Thompson, Variations on a question concerning the degrees of divisors of x^n - 1, Journal de Théorie des Nombres de Bordeaux, Vol. 26, No. 1 (2014), pp. 253-267.
Eric Weisstein's World of Mathematics, Finite Field.
Wikipedia, Finite field.

Cf. A000265, A002326, A007733, A007814.

Cf. A000010, A260653, A336504, A336505.

rep[v_, c_] := Flatten @ Table[ConstantArray[v[[i]], {c[[i]]}], {i, Length[c]}]; mo[n_, p_] := MultiplicativeOrder[p, n/p^IntegerExponent[n, p]]; ppQ[n_, p_] := Module[{d = Divisors[n]}, m = mo[#, p] & /@ d; ns = EulerPhi[d]/m; r = rep[m, ns]; Min @ Rest @ CoefficientList[Series[Product[1 + x^r[[i]], {i, Length[r]}], {x, 0, n}], x] >  0]; Select[Range[200], ppQ[#, 2] &]

A036260 Numbers k > 1 such that k mod ord2(k) is even, where ord2(k) is the order of 2 mod k.

Original entry on oeis.org

2921, 3017, 3473, 3479, 5767, 5969, 6167, 6377, 6497, 6913, 7223, 7519, 7567, 7751, 9017, 9271, 10199, 10447, 11431, 11929, 12719, 13439, 13609, 14513, 16583, 17009, 17143, 18631, 18809, 19313, 20737, 21119, 22337, 22351, 22537

Offset: 1

David W. Wilson

nonn

These are all composite since for prime p, ord2(p) | phi(p) = p-1, whence p mod ord2(p) = 1.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A002326, A007733, A036259.

Select[Range[3, 23000, 2], EvenQ[Mod[#, MultiplicativeOrder[2, #]]] &] (* Amiram Eldar, Jul 30 2020 *)

Offset corrected by Amiram Eldar, Jul 30 2020

A117987 Number of functions f:[n]->[n] such that f[(2x) mod n]=[2f(x)] mod n for all x in [n], for n=1,2,3,... Here [n] denotes {0,1,2,...,n-1}.

Original entry on oeis.org

1, 2, 3, 8, 5, 24, 49, 128, 27, 160, 11, 1536, 13, 6272, 10125, 32768, 289, 13824, 19, 163840, 64827, 22528, 529, 6291456, 125, 106496, 729, 102760448, 29, 331776000, 887503681, 2147483648, 107811, 37879808, 300125, 3623878656, 37, 9961472

Offset: 1

John W. Layman, Apr 11 2006

nonn

See A117986 and A117988 for results on other modular functional equations.

Cf. A117986, A117988.

{ A117987(n) = my(m,r); m=n\2^valuation(n,2); r=2^(n-m); fordiv(znorder(Mod(2,m)),d, r *= gcd(m,2^d-1)^(sumdiv(d,q, moebius(d\q)*gcd(m,2^q-1) )\d); ); r } /* Max Alekseyev, Jun 11 2009 */

For n = 2^t * m with odd m, a(n) = 2^(n-m) * \sum_{d|A007733(n)} gcd(m,2^d-1)^{ \sum_{q|d} moebius(d/q) * gcd(m,2^q-1) / d }. - Max Alekseyev, Jun 11 2009

Extended by Max Alekseyev, Jun 11 2009

cp's OEIS Frontend

A037178 Longest cycle when squaring modulo n-th prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A256608 Longest eventual period of a^(2^k) mod n for all a.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A295740 Even pseudoprimes (A006935) that are not squarefree.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A292544 Numbers h such that 2^phi(h) == phi(h) (mod h).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A306231 Lexicographically earliest sequence of distinct positive terms such that for any n > 0 and any k > 0, floor((2^k) / a(n)) AND floor((2^k) / a(n+1)) = 0 (where AND denotes the bitwise AND operator).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A382173 a(n) is the sum of row n of A382172.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A296243 Numbers k such that the multiplicative order of 2 modulo k is even.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A336503 2-practical numbers: numbers m such that the polynomial x^m - 1 has a divisor of every degree <= m in the prime field F_2[x].

Views

Author

A117987 Number of functions f:[n]->[n] such that f[(2x) mod n]=[2f(x)] mod n for all x in [n], for n=1,2,3,... Here [n] denotes {0,1,2,...,n-1}.