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

Author

Juri-Stepan Gerasimov, Aug 27 2020

Keywords

• nonn

Comments

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

Examples

			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).
		

Links

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

Crossrefs

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

Cf. also A338189, A338190.

Programs

Magma

[#[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]];

PARI

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