A334006 -id:A334006 - cp's OEIS frontend

A337454 a(n) is the number of divisors of n such that the ratio (the number of nonnegative m < n such that m^d == m (mod n))/(the number of nonnegative m < n such that -m^d == m (mod n)) is also a divisor of n.

1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 5, 2, 4, 4, 5, 2, 6, 2, 5, 2, 4, 2, 7, 3, 4, 4, 5, 2, 8, 2, 6, 2, 4, 2, 9, 2, 4, 4, 7, 2, 6, 2, 5, 6, 4, 2, 9, 3, 6, 4, 5, 2, 8, 2, 7, 2, 4, 2, 9, 2, 4, 5, 7, 2, 6, 2, 5, 2, 6, 2, 10, 2, 4, 6, 5, 1, 8, 2, 9, 5, 4, 2, 9, 4, 4, 4, 7, 2, 12, 4, 5, 2, 4, 2, 11

Offset: 1

Juri-Stepan Gerasimov, Aug 27 2020

nonn

a(n) is the number of ordered pairs (x,y) of divisors of n such that the ratio (the number of nonnegative m < n such that m^x == m (mod n)) / (the number of nonnegative m < n such that -m^x == m (mod n)) is equal to y. These pairs of divisors of each n define the direction of the arcs of some directed graph, the vertices of the number a(n) of which are indicated by the corresponding values of the divisors.
1 <= a(n) <= tau(n) where tau(n) is the number of divisors of n.
The boundary sequences of this relation are A338189 (numbers i such that a(i) = 1) and A338190 (numbers j such that a(j) = tau(j)).
Furthermore, for any nonnegative k, 1 <= the ratio (the number of nonnegative m < n such that m^k == m (mod n)) / (the number of nonnegative m < n such that -m^k == m (mod n)) <= n.
The number of divisors d such that A334006(n,d) is also a divisor of n. - Peter Kagey, Sep 09 2020

			a(1) = 1 solution is pair (x,y) of divisors of n = 1 is (1,1).
a(2) = 2 solutions are pairs (x,y) of divisors of n = 2 are (1,1) and (2,1).
a(3) = 2 solutions are pairs (x,y) of divisors of n = 3 are (1,3) and (3,3).
a(4) = 3 solutions are pairs (x,y) of divisors of n = 4 are (1,2), (2,1) and (4,1).

Michel Marcus, Table of n, a(n) for n = 1..5000

Cf. A000005, A001317, A019434, A334006, A336664, A337454.

Cf. also A338189, A338190.

[#[d: d in Divisors(n) | Denominator(n*#[m: m in [0..n-1] | -m^d mod n eq m]/#[m: m in [0..n-1] | m^d mod n eq m]) eq 1]: n in [1..96]];

a(n) = sumdiv(n, d, n % (sum(m=0, n-1, Mod(m, n)^d == m)/sum(m=0, n-1, Mod(-m, n)^d == m)) == 0); \\ Michel Marcus, Aug 30 2020

A336664 Number of distinct divisors d of n with the property that d = (the number of nonnegative bases m < n such that m^k == m (mod n))/(the number of nonnegative bases m < n such that -m^k == m (mod n)) for some nonnegative k.

Original entry on oeis.org

1, 1, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 3, 2, 2, 3, 2, 2, 2, 2, 2, 2, 3, 2, 3, 2, 2, 3, 2, 2, 2, 2, 3, 3, 2, 2, 3, 3, 2, 2, 2, 2, 4, 2, 2, 2, 3, 3, 3, 2, 2, 3, 3, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 4, 2, 2, 3, 2, 3, 3, 2, 2, 2, 3, 2, 3, 2, 2, 4, 3, 2, 2, 2, 3, 2

Offset: 1

Juri-Stepan Gerasimov, Jul 29 2020

nonn

For any k >= 0, the value of (the number of nonnegative bases m < n such that m^k == m (mod n))/(the number of nonnegative bases m < n such that -m^k == m (mod n)) is the value of some part of n, and is equal or unequal to the value of some divisor of n. Starting with k = 2, these infinite sequences of the parts of n are periodic with a period equal to A002322(n) (or A000010(n)). Also these sequences are different, but among n there are pairs of numbers (1 and 2, 3 and 6, ...) for which they are the same.
For n >= 1, minimal d is equal to 1 and maximal d is equal to A026741(n).
If n: 1, 2, 3, 5, 6, 10, 15, 17, 30, 34, 51, 85, 102, ..., then d = (the number of nonnegative bases m < n such that m^k = m)/(the number of nonnegative bases m < n such that -m^k = m) for all nonnegative k.

			For n = 1 the a(1) = 1 solution d is 1 (k = 0),
n = 2 the a(2) = 1 solution d is 1 (k = 0),
n = 3 the a(3) = 2 solutions d are 1 (k = 0) and 3 (k = 1),
n = 4 the a(4) = 2 solutions d are 1 (k = 0) and 2 (k = 1),
n = 5 the a(5) = 2 solutions d are 1 (k = 0) and 5 (k = 1),
n = 6 the a(6) = 2 solutions d are 1 (k = 0) and 3 (k = 1),
n = 7 the a(7) = 2 solutions d are 1 (k = 0) and 7 (k = 1),
n = 8 the a(8) = 2 solutions d are 1 (k = 0) and 4 (k = 1),
n = 9 the a(9) = 3 solutions d are 1 (k = 0), 3 (k = 3) and 9 (k = 1).

Antti Karttunen, Table of n, a(n) for n = 1..3755

Cf. A000010, A002322, A026741, A334006.

T(n, k) = sum(m=0, n-1, Mod(m, n)^k == m)/sum(m=0, n-1, Mod(-m, n)^k == m); \\ A334006
vec(n) = vecsort(vector(n, k, T(n,k-1)),,8);
a(n) = { my(v=vec(n)); sumdiv(n, d, vecsearch(v, d) != 0); }; \\ Michel Marcus, Aug 27 2020, edited for speed by Antti Karttunen, Dec 13 2021

A337632 Triangle read by rows: T(n,k) is the number of nonnegative integers m < n such that m^k - m == 0 (mod n), where 0 <= k < n.

Original entry on oeis.org

1, 1, 2, 1, 3, 2, 1, 4, 2, 3, 1, 5, 2, 3, 2, 1, 6, 4, 6, 4, 6, 1, 7, 2, 3, 4, 3, 2, 1, 8, 2, 5, 2, 5, 2, 5, 1, 9, 2, 3, 4, 3, 2, 7, 2, 1, 10, 4, 6, 4, 10, 4, 6, 4, 10, 1, 11, 2, 3, 2, 3, 6, 3, 2, 3, 2, 1, 12, 4, 9, 4, 9, 4, 9, 4, 9, 4, 9, 1, 13, 2, 3, 4, 5, 2

Offset: 1

Peter Kagey, Sep 12 2020

			Triangle begins:
  n\k| 0   1  2  3  4   5  6  7  8   9
  ---+--------------------------------
   1 | 1;
   2 | 1,  2;
   3 | 1,  3, 2;
   4 | 1,  4, 2, 3;
   5 | 1,  5, 2, 3, 2;
   6 | 1,  6, 4, 6, 4,  6;
   7 | 1,  7, 2, 3, 4,  3, 2;
   8 | 1,  8, 2, 5, 2,  5, 2, 5;
   9 | 1,  9, 2, 3, 4,  3, 2, 7, 2;
  10 | 1, 10, 4, 6, 4, 10, 4, 6, 4, 10;
...
T(10,2) = 4 because
0^2 - 0 == 0 (mod 10),
1^2 - 1 == 0 (mod 10),
5^2 - 5 == 0 (mod 10), and
6^2 - 6 == 0 (mod 10).

Peter Kagey, Table of n, a(n) for n = 1..10011 (first 141 rows, flattened)

Cf. A334006, A337633.

a337632t n k = length $ filter (\m -> (m^k - m) `mod` n == 0) [0..n-1]

[[#[m: m in [0..n-1] | m^k mod n eq m]: k in [0..n-1]]: n in [1..17]]; // Juri-Stepan Gerasimov, Oct 12 2020

T(n,k) = sum(m=0, n-1, Mod(m,n)^k == Mod(m,n)); \\ Michel Marcus, Sep 13 2020

T(n,k) = A334006(n,k) * A337633(n,k).

A337633 Triangle read by rows: T(n,k) is the number of nonnegative integers m < n such that m^k + m == 0 (mod n), where 0 <= k < n.

Original entry on oeis.org

1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 1, 2, 3, 2, 1, 2, 4, 2, 4, 2, 1, 1, 2, 1, 4, 1, 2, 1, 2, 2, 1, 2, 1, 2, 1, 1, 1, 2, 1, 4, 1, 2, 1, 2, 1, 2, 4, 6, 4, 2, 4, 6, 4, 2, 1, 1, 2, 1, 2, 1, 6, 1, 2, 1, 2, 1, 2, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 1, 1, 2, 3, 4, 1, 2, 7, 2

Offset: 1

Peter Kagey, Sep 12 2020

			Triangle begins:
  n\k| 0  1  2  3  4  5  6  7  8  9
  ---+-----------------------------
   1 | 1;
   2 | 1, 2;
   3 | 1, 1, 2;
   4 | 1, 2, 2, 1;
   5 | 1, 1, 2, 3, 2;
   6 | 1, 2, 4, 2, 4, 2;
   7 | 1, 1, 2, 1, 4, 1, 2;
   8 | 1, 2, 2, 1, 2, 1, 2, 1;
   9 | 1, 1, 2, 1, 4, 1, 2, 1, 2;
  10 | 1, 2, 4, 6, 4, 2, 4, 6, 4, 2;
...
T(10, 2) = 4 because
0^2 + 0 == 0 (mod 10),
4^2 + 4 == 0 (mod 10),
5^2 + 5 == 0 (mod 10), and
9^2 + 9 == 0 (mod 10).

Peter Kagey, Table of n, a(n) for n = 1..10011 (first 141 rows, flattened)

Cf. A333570, A334006, A337632.

a337633t n k = length $ filter (\m -> (m^k + m) `mod` n == 0) [0..n-1]

[[#[m: m in [0..n-1] | -m^k mod n eq m]: k in [0..n-1]]: n in [1..17]]; // Juri-Stepan Gerasimov, Oct 12 2020

T(n,k) = A337632(n,k)/A334006(n,k).

A340281 a(n) is the smallest prime p such that the number of distinct values of the ratio (number of nonnegative m < p such that m^k == m (mod p))/(number of nonnegative m < p such that -m^k == m (mod p)) is equal to n for some nonnegative k.

Original entry on oeis.org

2, 3, 7, 19, 31, 163, 127, 1459, 211, 883, 811, 472393, 631, 8503057, 32077, 4051, 2311, 86093443, 4951, 6347497291777, 10531, 36451, 1299079, 251048476873, 8191, 388963, 5314411, 22051, 51031, 596046447753906250001, 28351, 411782264189299, 24571, 5904901

Offset: 1

Juri-Stepan Gerasimov, Jan 02 2021

nonn

a(n) is the least prime p such that there are n distinct terms in the p-th row of A334006.
Conjecture: a(n) is the smallest prime p such that the number of distinct values of the ratio T(p, k) = (number of nonnegative m < p such that m^k == m (mod p))/(number of nonnegative m < p such that -m^k == m (mod p)) is equal to n for some 0 <= k <= floor((p + 2)/3).
Proof: for k > 1, iff t is a k-th power residue mod p, the number of nonnegative m < p such that m^k == t (mod p) is gcd(k, p - 1). Thus, the ratio T(p, 1+x) = T(p, 1+gcd(x, p-1)) and T(p, 2*t) = T(p, (p+1)/2) = 1. For odd prime p and 0 <= k < p - 1, notice that if k is an odd number of the form 1 + gcd(x, p-1) and x != (p - 1)/2, then k <= floor((p + 2)/3). - Jinyuan Wang, Jan 23 2021
For n >= 2, a(n) is the least prime p such that p - 1 has n - 1 odd divisors. - Jinyuan Wang, Jan 23 2021

			A334006 triangle begins:
   1 | 1;
   2 | 1, 1;   : 1 distinct value
   3 | 1, 3, 1;   : 2 distinct values
   4 | 1, 2, 1, 3;
   5 | 1, 5, 1, 1, 1;   : 2 distinct values
   6 | 1, 3, 1, 3, 1, 3;
   7 | 1, 7, 1, 3, 1, 3, 1;   : 3 distinct values

Seth A. Troisi, Table of n, a(n) for n = 1..200

Cf. A001227, A019434, A058500, A074781, A334006.

T(n, k) = sum(m=0, n-1, Mod(m, n)^k == m)/sum(m=0, n-1, -Mod(m, n)^k == m); \\ A334006
a(n) = my(p=2); while (#Set(vector(p, k, T(p,k))) != n, p = nextprime(p+1)); p; \\ Michel Marcus, Jan 21 2021

lista(nn, show=50) = my(c, v=vector(show)); v[1]=2; forprime(p=3, nn, c=1+numdiv(p\2^valuation(p-1, 2)); if(c<=show && !v[c], v[c]=p)); v; \\ Jinyuan Wang, Jan 23 2021

More terms from Jinyuan Wang, Jan 23 2021

Typo in a(34) corrected by Seth A. Troisi, May 22 2022

A337820 Array read by antidiagonals: T(n,k) (n >= 1, k >= 0) is the ratio (the number of nonnegative bases m < n such that m^k == m (mod n))/(the number of nonnegative bases m < n such that -m^k == m (mod n)).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 2, 1, 1, 1, 1, 5, 1, 3, 1, 1, 1, 3, 1, 3, 1, 1, 1, 1, 7, 1, 1, 1, 3, 1, 1, 1, 4, 1, 3, 1, 3, 1, 1, 1, 1, 9, 1, 3, 1, 5, 1, 3, 1, 1, 1, 5, 1, 5, 1, 3, 1, 3, 1, 1, 1, 1, 11, 1, 3, 1, 3, 1, 1, 1, 3, 1, 1, 1, 6, 1, 1, 1, 5, 1, 3, 1, 3, 1, 1, 1, 1, 13, 1, 3, 1, 3

Offset: 1

Juri-Stepan Gerasimov, Sep 23 2020

Array read by antidiagonals: T(n,k) (n >=1, k >= 0) is part of n of the form (the number of nonnegative bases m < n such that m^k == m (mod n))/(the number of nonnegative bases m < n such that -m^k == m (mod n)).

			The initial rows of the array are:
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
  1, 1, 3, 2, 5, 3, 7, 4, 9, 5, 11, 6, 13, ...
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
  1, 1, 3, 3, 1, 3, 3, 5, 3, 1, 3, 9, 1, ...
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
  1, 1, 3, 3, 5, 3, 3, 5, 3, 5, 3, 9, 5, ...
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
  1, 1, 3, 3, 1, 3, 7, 5, 7, 1, 3, 9, 1, ...
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
  1, 1, 3, 3, 5, 3, 3, 5, 3, 5, 3, 9, 5, ...
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
  1, 1, 3, 3, 1, 3, 3, 5, 3, 1, 3, 9, 1, ...
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
  1, 1, 3, 3, 5, 3, 7, 5, 7, 5, 3, 9, 5, ...
The initial antidiagonals are:
     1,
     1,  1,
     1,  1, 1,
     1,  3, 1, 1,
     1,  2, 1, 1, 1,
     1,  5, 1, 3, 1, 1,
     1,  3, 1, 3, 1, 1, 1,
     1,  7, 1, 1, 1, 3, 1, 1,
     1,  4, 1, 3, 1, 3, 1, 1, 1,
     1,  9, 1, 3, 1, 5, 1, 3, 1, 1,
     1,  5, 1, 5, 1, 3, 1, 3, 1, 1, 1,
     1, 11, 1, 3, 1, 3, 1, 1, 1, 3, 1, 1,
     1,  6, 1, 1, 1, 5, 1, 3, 1, 3, 1, 1, 1,
     1, 13, 1, 3, 1, 3, 1, 7, 1, 5, 1, 3, 1, 1,
...

Columns 0-2: A000012, A026741, A000012.

Cf. A000010, A000012, A000027, A002322, A182816, A333570, A334006, A334597, A336664.

/* As triangle */ [[#[m: m in [0..n-k-1] | m^k mod (n-k) eq m]/
#[m: m in [0..n-k-1] | -m^k mod (n-k) eq m]: k in [0..n-1]]: n in [1..13]];

T(n, 2*k) = 1; 1 <= T(n, 2*k+1) <= n.

A337910 Integers of the form (the number of nonnegative bases m < n such that m^3 == m (mod n))/(the number of nonnegative bases m < n such that -m^3 == m (mod n)).

Original entry on oeis.org

1, 1, 3, 3, 1, 3, 3, 5, 3, 1, 3, 9, 1, 3, 3, 5, 1, 3, 3, 3, 9, 3, 3, 15, 1, 1, 3, 9, 1, 3, 3, 5, 9, 1, 3, 9, 1, 3, 3, 5, 1, 9, 3, 9, 3, 3, 3, 15, 3, 1, 3, 3, 1, 3, 3, 15, 9, 1, 3, 9, 1, 3, 9, 5, 1, 9, 3, 3, 9, 3, 3, 15, 1, 1, 3, 9, 9, 3, 3, 5, 3, 1, 3, 27, 1, 3, 3, 15, 1, 3, 3, 9, 9, 3, 3, 15

Offset: 1

Juri-Stepan Gerasimov, Sep 29 2020

All members of a(n) are odd numbers. For n > 3, 1 <= a(n) < n.

Cf. A026741, A008784, A002313, A002145, A334006.

[#[m: m in [0..n-1] | m^3 mod n eq m]/#[m: m in [0..n-1] | -m^3 mod n eq m]: n in [1..96]];

A336597 a(n) is the least number k of the form (the number of nonnegative bases m < n such that m^k == m (mod n))/(the number of nonnegative bases m < n such that -m^k == m (mod n)) dividing n, or 0 if no such k exists.

Original entry on oeis.org

1, 1, 3, 0, 5, 3, 7, 0, 3, 5, 11, 0, 13, 7, 3, 0, 17, 3, 19, 0, 0, 11, 23, 0, 5, 13, 3, 0, 29, 3, 31, 0, 0, 17, 7, 9, 37, 19, 3, 0, 41, 0, 43, 0, 3, 23, 47, 0, 7, 5, 3, 0, 53, 3, 11, 0, 0, 29, 59, 0, 61, 31, 9, 0, 0, 0, 67, 0, 0, 7, 71, 0, 73, 37, 3, 0, 0, 3, 79, 0, 3, 41, 83, 0, 5, 43, 3, 0, 89, 3

Offset: 1

Juri-Stepan Gerasimov, Jul 26 2020

nonn

Conjecture: For each natural number n, either there is a divisor k of the form (the number of nonnegative bases m < n such that m^k == m (mod n))/(the number of nonnegative bases m < n such that -m^k == m (mod n)) and it is unique, or it does not exist.

This has been checked up to at least 10^3.

Supersequence of A065091 and A002997. Cf. A334006.

[1] cat [&*[d: d in Divisors(n)]/&*[k: k in [1..n] | not #[m: m in [0..n-1] | m^k mod n eq m]/#[m: m in [0..n-1] | -m^k mod n eq m] eq k and n mod k eq 0] - 1 + #[k: k in [1..n] | #[m: m in [0..n-1] | m^k mod n eq m]/#[m: m in [0..n-1] | -m^k mod n eq m] eq k and n mod k eq 0]: n in [2..90]];

a(n) = {fordiv(n, d, if (d == sum(m=0, n-1, Mod(m,n)^d == m)/sum(m=0, n-1, Mod(-m,n)^d == m), return (d)););} \\ Michel Marcus, Aug 20 2020

cp's OEIS Frontend

A337454 a(n) is the number of divisors of n such that the ratio (the number of nonnegative m < n such that m^d == m (mod n))/(the number of nonnegative m < n such that -m^d == m (mod n)) is also a divisor of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

PARI

A336664 Number of distinct divisors d of n with the property that d = (the number of nonnegative bases m < n such that m^k == m (mod n))/(the number of nonnegative bases m < n such that -m^k == m (mod n)) for some nonnegative k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A337632 Triangle read by rows: T(n,k) is the number of nonnegative integers m < n such that m^k - m == 0 (mod n), where 0 <= k < n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

Magma

PARI

Formula

A337633 Triangle read by rows: T(n,k) is the number of nonnegative integers m < n such that m^k + m == 0 (mod n), where 0 <= k < n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

Magma

Formula

A340281 a(n) is the smallest prime p such that the number of distinct values of the ratio (number of nonnegative m < p such that m^k == m (mod p))/(number of nonnegative m < p such that -m^k == m (mod p)) is equal to n for some nonnegative k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Extensions

A337820 Array read by antidiagonals: T(n,k) (n >= 1, k >= 0) is the ratio (the number of nonnegative bases m < n such that m^k == m (mod n))/(the number of nonnegative bases m < n such that -m^k == m (mod n)).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Magma

Formula

A337910 Integers of the form (the number of nonnegative bases m < n such that m^3 == m (mod n))/(the number of nonnegative bases m < n such that -m^3 == m (mod n)).

Views

Author

Keywords

Comments

Crossrefs

Programs

Magma

A336597 a(n) is the least number k of the form (the number of nonnegative bases m < n such that m^k == m (mod n))/(the number of nonnegative bases m < n such that -m^k == m (mod n)) dividing n, or 0 if no such k exists.

Views

Author

Keywords

Comments