A118106 -id:A118106 - cp's OEIS frontend

A328925 a(n) = A002322(n)/A118106(n); write n = Product_{i=1..t} p_i^e_i, then a(n) = A002322(n)/(lcm_{1<=i,j<=t,i!=j} ord(p_i,p_j^e_j)), where ord(a,r) is the multiplicative order of a modulo r, and A002322 is the Carmichael lambda (usually written as psi).

1, 1, 2, 2, 4, 1, 6, 2, 6, 1, 10, 1, 12, 2, 1, 4, 16, 1, 18, 1, 1, 1, 22, 1, 20, 1, 18, 1, 28, 1, 30, 8, 1, 2, 1, 1, 36, 1, 4, 1, 40, 1, 42, 1, 1, 2, 46, 1, 42, 1, 1, 1, 52, 1, 4, 1, 1, 1, 58, 1, 60, 6, 1, 16, 3, 1, 66, 2, 1, 1, 70, 1, 72, 1, 1, 1, 1, 1, 78, 1, 54, 2, 82, 1, 1, 3, 1

Offset: 1

Jianing Song, Oct 31 2019

nonn

It is easy to see that A118106(n) divides psi(n) = A002322(n).

If n = p^e for prime p, then A118106(p^e) = 1, so a(p^e) = A002322(p^e). The other n's such that a(n) > 1 are listed in A329062.

			A002322(14) = 6, while A118106(14) = 3, so a(14) = 2.

Cf. A002322, A118106, A328926 (indices of 1), A329062.

a(n) = A002322(n)/A118106(n) \\ See A002322 and A118106 for their programs

A329065 Smallest m_0 such that A118106(m_0) = n; smallest m_0 such that if we write m_0 = Product_{i=1..t} p_i^e_i, then lcm_{1<=i,j<=t, i!=j} ord(p_i,p_j^e_j) = n, where ord(a,r) is the multiplicative order of a modulo r.

Original entry on oeis.org

1, 6, 14, 10, 55, 18, 203, 34, 146, 22, 46, 26, 689, 86, 302, 51, 5759, 38, 955, 50, 98, 69, 94, 288, 505, 5462, 327, 58, 466, 77, 9305, 384, 5447, 309, 142, 74, 446, 2933, 158, 246, 3403, 129, 862, 115, 543, 141, 4702, 119, 5713, 453, 206, 106, 5671, 162, 605, 928, 687, 118

Offset: 1

Jianing Song, Nov 03 2019

nonn

For n != 1, 6, a(n) <= 2*A112927(n): suppose n != 1, 6, by Zsigmondy's theorem, 2^n - 1 has at least one primitive factor p. Here a primitive factor p means that ord(2,p) = n, where ord(a,r) is the multiplicative order of a modulo r. So we have A118106(2p) = lcm(ord(p,2),ord(2,p)) = lcm(1,n) = n. Specially, we have A118106(2*A112927(n)) = n for n != 1, 6.

There is another way to construct m such that A118106(m) = n > 1 (and usually this way generates smaller m's than the way above): let q be any prime factor of n, again, by Zsigmondy's theorem, q^n - 1 has at least one primitive factor p unless (n,q) = (6,2). Note that q^(p-1) == 1 (mod p), so q^gcd(p-1,n) == 1 (mod p). But n is the smallest positive number such that q^n == 1 (mod p), so gcd(p-1,n) = n. So we have A118106(pq) = lcm(ord(p,q),ord(q,p)) = lcm(1,n) = n. For example, if n = 5, then q = 5, p = 11, m = 55 (the way above gives A118106(62) = 5); if n = 7, then q = 7, p = 29, m = 203 (the way above gives A118106(254) = 7); if n = 13, then q = 13, p = 53, m = 689 (the way above gives A118106(16382) = 13). This gives a(q) <= q*A212552(q) for primes q.

			A118106(203) = 7; for any m < 203, A118106(m) is not equal to 7, so a(7) = 203.

Cf. A118106, A112927, A212552.

a(n) = for(k=1, oo, if(A118106(k)==n, return(k))) \\ See A118106 for its program

A118107 Period of the vector sequence d(n)^2^k mod n for k=1,2,3,..., where d(n) is the vector of divisors of n.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 4, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 4, 1, 2, 2, 1, 6, 2, 1, 1, 2, 1, 4, 2, 10, 1, 1, 1, 4, 1, 2, 1, 6, 4, 2, 6, 3, 1, 1, 1, 4, 2, 1, 1, 4, 1, 1, 10, 2, 1, 2, 1, 6, 4, 6, 4, 2, 1, 1, 1, 4, 1, 2, 1, 3, 3, 4, 1, 2, 2, 10, 4, 11, 6, 1, 1, 6, 4, 4

Offset: 1

T. D. Noe, Apr 13 2006

nonn

This sequence is related to the period of sigma_(2^k)(n) mod n, which is important in studying the numbers n dividing sigma_(2^k)(n) for all k>0. See A066292 and A118076. Note that a(n)=1 if n is a power of a prime.

			See A118106 for an example involving d(n)^k.

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

Cf. A118106 (period of the vector sequence d(n)^k mod n).

Table[d=Divisors[n]; k=0; found=False; While[i=0; While[i

A118107(n) = { my(divs=apply(d -> (d%n),divisors(n)), odivs = Vec(divs), vs = Map()); mapput(vs, odivs, 0); for(k=1,oo,divs = vector(#divs,i,(divs[i]*divs[i])%n); if(mapisdefined(vs, divs), return(k-mapget(vs, divs)), mapput(vs, divs, k))); }; \\ Antti Karttunen, Sep 23 2018

A328926 Numbers k such that A328925(k) = 1; numbers k such that if we write k = Product_{i=1..t} p_i^e_i, then lcm_{1<=i,j<=t,i!=j} ord(p_i,p_j^e_j) = A002322(k), where ord(a,r) is the multiplicative order of a modulo r, and A002322 is the Carmichael lambda (usually written as psi).

Original entry on oeis.org

1, 2, 6, 10, 12, 15, 18, 20, 21, 22, 24, 26, 28, 30, 33, 35, 36, 38, 40, 42, 44, 45, 48, 50, 51, 52, 54, 56, 57, 58, 60, 63, 66, 69, 70, 72, 74, 75, 76, 77, 78, 80, 84, 85, 87, 88, 90, 91, 92, 93, 96, 99, 100, 102, 104, 105, 106, 108, 110, 114, 115, 116, 118, 119, 120, 122

Offset: 1

Jianing Song, Oct 31 2019

nonn

Numbers such that A118106(k) = A002322(k).
{a(n)} intersect A000961 = {1, 2}.
{a(n)} union A329062 = N* \ A000961 U {1, 2}.
If k = Product_{i=1..t} p_i^e_i (t > 1), where {p_i} are primes such that p_i is a lambda primitive root modulo p_j^e_j for all i != j (that is to say, ord(p_i,p_j^e_j) = A002322(p_j^e_j), where ord(a,r) is the multiplicative order of a modulo r), then k is here, as A118106(k) = A002322(k). For example, k = 2^5 * 5 * 13.

			For k = 115 = 5 * 23, A118106(115) = lcm(ord(23,5),ord(5,23)) = lcm(4,22) = 44 = A002322(115), so 115 is a term.
For k = 973 = 7 * 139, A118106(973) = lcm(ord(139,7),ord(7,139)) = lcm(6,69) = 138 = A002322(973), so 973 is a term.

Cf. A118106, A002322, A326925, A329062, A000961.

isA328926(n) = (A002322(n) == A118106(n)) \\ See A002322 and A118106 for their programs

A329062 Numbers k that are not prime powers (i.e., not in A000961) such that A328925(k) > 1; numbers k such that if we write k = Product_{i=1..t} p_i^e_i , then t > 1, and lcm_{1<=i,j<=t, i!=j} ord(p_i,p_j^e_j) < A002322(k), where ord(a,r) is the multiplicative order of a modulo r, and A002322 is the Carmichael lambda (usually written as psi).

Original entry on oeis.org

14, 34, 39, 46, 55, 62, 65, 68, 82, 86, 94, 95, 98, 111, 112, 117, 123, 124, 133, 136, 142, 145, 146, 153, 155, 158, 164, 172, 175, 178, 183, 194, 201, 203, 205, 206, 209, 218, 219, 221, 224, 226, 248, 253, 254, 259, 272, 274, 275, 287, 291, 292, 295, 299, 301, 302, 305, 309

Offset: 1

Jianing Song, Nov 02 2019

nonn

Write psi = A002322, b = A118106. These are numbers k that are not prime powers such that b(k) < psi(k).
If k = Product_{i=1..t} p_i^e_i (t > 1), where {p_i} are distinct odd primes such that p_i is a quadratic residue modulo p_j for all i != j, then k is here, as b(k) | psi(k)/2.
If k = 2 * Product_{i=1..t} p_i^e_i, where {p_i} are distinct odd primes such that p_i is a quadratic residue modulo p_j for all i != j, and p_i == 1, 7 (mod 8), then k is here. For example, k = 2p, where p == 1, 7 (mod 8).
If k = 2^e * Product_{i=1..t} p_i^e_i (e > 1), where {p_i} are distinct odd primes such that p_i is a quadratic residue modulo p_j for all i != j, and p_i == 1 (mod 8), then k is here. For example, k = 2^e*p, where p == 1 (mod 8).
If k = p_1^e_1 * p_2^e_2, where p_1 is not a primitive root modulo p_2^e_2, p_2 is not a primitive root modulo p_1^e_1, then k is not necessarily here: for k = 3^2 * 67 = 603, 3 is not a primitive root modulo 67, 67 is not a primitive root modulo 3^2, but b(603) = psi(603) = 66. Conversely, if p_1 is a primitive root modulo p_2^e_2, then k can still be here: for k = 3^2 * 17 = 153, 3 is a primitive root modulo 17, but b(153) = 16 while psi(153) = 48.
If k is an odd number, then 4k is here if and only if 8k is also here. Write k = Product_{i=1..t} p_i^e_i, then b(4k) = lcm(lcm_{i=1..t} ord(p_i,4),lcm_{i=1..t} ord(2,p_i^e_i),b(k)), b(8k) = lcm(lcm_{i=1..t} ord(p_i,8),lcm_{i=1..t} ord(2,p_i^e_i),b(k)). It is easy to see that lcm(ord(p_i,4),ord(2,p_i^e_i)) = lcm(ord(p_i,8),ord(2,p_i^e_i)), so b(4k) = b(8k). Note that psi(4k) = psi(8k).
If k is an odd number such that 4k is here, then 16k is also here (but the converse is not true). Write k = Product_{i=1..t} p_i^e_i, N = lcm(lcm_{i=1..t} ord(2,p_i^e_i),b(k)), then b(4k) = lcm(lcm_{i=1..t} ord(p_i,4),N), b(16k) = lcm(lcm_{i=1..t} ord(p_i,16),N) = b(4k) or b(4k)*2 or b(4k)*4. Note that psi(16k) = lcm(psi(4k),4). If we have b(4k) < psi(4k) and b(16k) = psi(16k), let M = psi(k), then:
Case (a): M == 2 (mod 4), then b(16k) = psi(16k) = 2*psi(4k) = 2M, and b(4k) = b(16k)/4 = M/2 which is an odd number, so ord(2,p_i^e_i) is odd for all i, so p_i == 1, 7 (mod 8), which gives ord(p_i,16) <= 2*ord(p_i,4). As a result, b(16k) <= 2*b(4k), a contradiction!
Case (b): M == 0 (mod 4), then b(16k) = psi(16k) = psi(4k) = M. If N is divisible by 4, then b(4k) = b(16k) = N, a contradiction. So 4 does not divide N, we have v(M,2) = v(lcm(lcm_{i=1..t} ord(p_i,16),N),2) <= 2, but 4 | M, so v(M,2) = 2, where v(,2) is the 2-adic valuation. As a result, there must exist p_i congruent to 5 mod 8 to make v(M,2) = 2, then 4 | ord(2,p_i^e_i), so 4 | N, a contradiction!
{a(n)} union A328926 = N* \ A000961 U {1, 2}.

			Let ord(a,r) be the multiplicative order of a modulo r.
For k = 175 = 5^2 * 7, b(175) = lcm(ord(7,5^2),ord(5,7)) = lcm(4,6) = 12, while psi(175) = lcm(20,6) = 60, so 175 is a term.
For k = 410 = 2 * 5 * 41, b(410) = lcm(ord(5,2),ord(41,2),ord(2,5),ord(41,5),ord(2,41),ord(5,41)) = 20, while psi(410) = lcm(1,4,40) = 40, so 410 is a term.

Cf. A118106, A002322, A326925, A326926, A000961.

isA329062(n) = !isprimepower(n) && (A002322(n) > A118106(n)) \\ See A002322 and A118106 for their programs

cp's OEIS Frontend

A328925 a(n) = A002322(n)/A118106(n); write n = Product_{i=1..t} p_i^e_i, then a(n) = A002322(n)/(lcm_{1<=i,j<=t,i!=j} ord(p_i,p_j^e_j)), where ord(a,r) is the multiplicative order of a modulo r, and A002322 is the Carmichael lambda (usually written as psi).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A329065 Smallest m_0 such that A118106(m_0) = n; smallest m_0 such that if we write m_0 = Product_{i=1..t} p_i^e_i, then lcm_{1<=i,j<=t, i!=j} ord(p_i,p_j^e_j) = n, where ord(a,r) is the multiplicative order of a modulo r.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A118107 Period of the vector sequence d(n)^2^k mod n for k=1,2,3,..., where d(n) is the vector of divisors of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A328926 Numbers k such that A328925(k) = 1; numbers k such that if we write k = Product_{i=1..t} p_i^e_i, then lcm_{1<=i,j<=t,i!=j} ord(p_i,p_j^e_j) = A002322(k), where ord(a,r) is the multiplicative order of a modulo r, and A002322 is the Carmichael lambda (usually written as psi).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI