A006694 -id:A006694 - cp's OEIS frontend

A221855 Number of cyclotomic cosets of 13 mod 10^n.

4, 12, 30, 72, 130, 204, 294, 400, 522, 660, 814, 984, 1170, 1372, 1590, 1824, 2074, 2340, 2622, 2920, 3234, 3564, 3910, 4272, 4650, 5044, 5454, 5880, 6322, 6780, 7254, 7744, 8250, 8772, 9310, 9864, 10434, 11020, 11622, 12240, 12874, 13524, 14190, 14872, 15570, 16284, 17014, 17760, 18522, 19300

Offset: 1

V. Raman, Jan 28 2013

			a(2) = 12 because there are 12 cyclotomic cosets of 13 mod 100:
{1, 13, 69, 97, 61, 93, 9, 17, 21, 73, 49, 37, 81, 53, 89, 57, 41, 33, 29, 77}
{3, 39, 7, 91, 83, 79, 27, 51, 63, 19, 47, 11, 43, 59, 67, 71, 23, 99, 87, 31}
{2, 26, 38, 94, 22, 86, 18, 34, 42, 46, 98, 74, 62, 6, 78, 14, 82, 66, 58, 54}
{4, 52, 76, 88, 44, 72, 36, 68, 84, 92, 96, 48, 24, 12, 56, 28, 64, 32, 16, 8}
{5, 65, 45, 85}
{15, 95, 35, 55}
{25}
{75}
{10, 30, 90, 70}
{20, 60, 80, 40}
{50}
{0}

Index entries for linear recurrences with constant coefficients, signature (3, -3, 1).

Cf. A006694, A220468.

a[n_]:=DivisorSum[10^n,EulerPhi[#]/MultiplicativeOrder[13,#]&]; Array[a,50] (* Ray Chandler, Jul 03 2023, after Jean-François Alcover *)

for(n=1,50,print1(sumdiv(10^n, d, eulerphi(d)/znorder(Mod(13, d)))", "))

a(n) = A220018(n) for n = 1.
a(n) = A220018(n) + 1 for all n >= 2.
Conjecture: a(n) = 2*n*(4*n-7) for n>2. a(n) = 3*a(n-1)-3*a(n-2)+a(n-3) for n>5. G.f.: 2*x*(4*x^4-7*x^3-3*x^2-2) / (x-1)^3. - Colin Barker, Apr 14 2013

A333468 Length of the largest disjoint cycle of the permutation that results from the composition of first n circular shifts.

Original entry on oeis.org

1, 2, 2, 3, 5, 6, 3, 4, 9, 4, 7, 10, 9, 14, 4, 5, 7, 18, 8, 10, 7, 7, 14, 11, 6, 26, 12, 9, 29, 30, 5, 6, 33, 11, 21, 6, 11, 15, 22, 27, 41, 6, 17, 8, 8, 7, 22, 24, 15, 50, 28, 8, 53, 18, 22, 14, 25, 9, 15, 55, 14, 50, 6, 7, 65, 11, 19, 34, 69, 23, 35, 14, 22, 74, 10

Offset: 1

Richard Locke Peterson, Mar 22 2020

nonn

Size of the largest part of the partition of n that is associated with the cycle structure of the permutation given by the permutation product (1)*(1,2)*(1,2,3)*...*(1,2,3,...n) after the product is rewritten as the product of disjoint cycles, where * means functional composition, and the permutations are written in cycle form.
Also see Circular shift on Wikipedia.
For n>1, a(n) is always greater than 1, since the given product can never be the identity permutation on the set {1,2,...,n}, which is the only permutation associated with the partition <1,1,...,1> (1 repeated n times).
Connections: The image of 1 in each resulting permutation appears to be the same as the numbers in A003602. The number of parts in the partition associated with each resulting permutation appear to match the numbers in A006694.
The LCM of all cycle lengths gives A051732(n+1). - Alois P. Heinz, Apr 08 2020

			For n=3, the permutation (1)*(1,2)*(1,2,3)=(1)*(2,3), which is associated with the partition <2,1> of 3. The size of the largest part is 2, so a(3)=2.
For n=11, the permutation (1)*(1,2)*..*(1,2,..11)=(1,2,7,5)*(3,4,8,10,11,6,9) when rewritten as the product of disjoint cycles, which is associated with the partition <7,4> of 11. The size of the largest part is 7, so a(11)=7.

Alois P. Heinz, Table of n, a(n) for n = 1..3000
Wikipedia, Circular shift

Cf. A003602, A006694, A051732, A071642, A163782.

Follow(s, f)={my(t=f(s), k=1); while(t>s, k++; t=f(t)); if(s==t, k, 0)}
mkp(n)={my(v=vector(n,i,i)); for(k=1, n, my(t=v[1]); for(i=1, k-1, v[i]=v[i+1]); v[k]=t); v}
a(n)={my(v=mkp(n), m=0); for(i=1, n, m=max(m, Follow(i, j->v[j]))); m} \\ Andrew Howroyd, Mar 27 2020

a(n) = n <=> n in { A163782 } union { 1 }. - Alois P. Heinz, Apr 08 2020

Terms a(20) and beyond from Andrew Howroyd, Mar 27 2020

A366494 a(n) is the number of cycles of the map f(x) = 10x mod (10n - 1).

Original entry on oeis.org

8, 1, 1, 8, 2, 1, 5, 6, 2, 53, 1, 4, 8, 3, 1, 14, 4, 1, 41, 2, 16, 29, 1, 34, 8, 49, 1, 26, 2, 7, 11, 16, 4, 5, 3, 2, 80, 1, 1, 26, 2, 1, 83, 2, 14, 29, 9, 2, 8, 1, 1, 14, 2, 27, 17, 16, 2, 5, 9, 2, 14, 1, 25, 26, 16, 1, 5, 8, 14, 5, 1, 2, 32, 3, 5, 50, 4, 17, 5, 4, 4, 143

Offset: 1

Hillel Wayne, Oct 10 2023

nonn

Taking the length of each orbit that starts from f(0)=1 gives the sequence A128858.
Equivalently, the number of cyclotomic cosets of 10 mod (10*n - 1). See A006694.
Map is the Multiply-with-carry algorithm with a=n, b=10, and c=1.

			For a(4) the 8 cycles are:
  (1 10 22 25 16 4)
  (2 20 5 11 32 8)
  (3 30 27 36 9 12)
  (6 21 15 33 18 24)
  (7 31 37 19 34 28)
  (13)
  (14 23 35 38 29 17)
  (26)

Hillel Wayne, Table of n, a(n) for n = 1..1002
George Marsaglia, Random Number Generators, Journal of Modern Applied Statistical Methods, Volume 2, Issue 1 (2003).
Kenneth Shum, Cyclotomic cosets.

Cf. A006694, A023142, A128858, A128857.

a(n)=sumdiv(10*n-1, d, eulerphi(d)/znorder(Mod(10, d)))-1;
vector(100, n, a(n-1)) \\ Joerg Arndt, Jan 22 2024

def get_num_orbits(n: int) -> int:
    orbits = 0
    mod = 10*n - 1
    seen = set()
    for i in range(1, mod):
        if i not in seen:
            seen.add(i)
            orbits += 1
        x = 10*i % mod
        while x != i:
            seen.add(x)
            x = 10*x % mod
    return orbits

from sympy import totient, n_order, divisors
def A366494(n): return sum(totient(d)//n_order(10,d) for d in divisors(10*n-1,generator=True) if d>1) # Chai Wah Wu, Apr 09 2024

A139042 Composite numbers c for which A064287((c-1)/2)=1.

Original entry on oeis.org

15, 39, 55, 87, 95, 111, 143, 159, 183, 295, 303, 319, 335, 407, 415, 447, 519, 535, 543, 551, 583, 591, 655, 695, 767, 807, 815, 879, 895, 951, 1007, 1047, 1055, 1079, 1119, 1135, 1167, 1263, 1383, 1391, 1527, 1623, 1639, 1671, 1703, 1711, 1735, 1839, 1895, 1903, 1919, 1943

Offset: 1

Vladimir Shevelev, Jun 01 2008

nonn

Is there an n for which A006694((a(n)-1)/2) is not equal to 4?

Cf. A064287, A006694, A001122.

More terms (using A064287 b-file) from Michel Marcus, Dec 16 2018

A140197 A137576((k-1)/2) for composite numbers k from A141229.

Original entry on oeis.org

55, 301, 3631, 6085, 19495, 70645, 147853, 438205, 605695, 669781, 888823, 1694695, 3060301, 3640783, 6692791, 7998895, 9857245, 12912535, 15443365, 17109895, 17690941, 22819693, 28048231, 34936663, 58178245, 75203725, 95263573, 124984543, 127160245, 155267965

Offset: 1

Vladimir Shevelev, Jun 15 2008

nonn

Cf. A137576, A141229, A006694, A002326.

r[n_] := EulerPhi[n]/MultiplicativeOrder[2, n]; d[n_] := DivisorSum[n, r[#] &]; f[n_] := (m = MultiplicativeOrder[2, n])*d[n] - m + 1; f /@ Select[Range[10^5], CompositeQ[#] && Total@(r /@ Divisors[#]) - 1 == 3 &] (* Amiram Eldar, Sep 12 2019 *)

More terms from Amiram Eldar, Sep 12 2019

A140198 A002326((k-1)/2) for composite numbers k from A141229.

Original entry on oeis.org

18, 100, 1210, 2028, 6498, 23548, 49284, 146068, 201898, 223260, 296274, 564898, 1020100, 1213594, 2230930, 2666298, 3285748, 4304178, 5147788, 5703298, 5896980, 7606564, 9349410, 11645554, 19392748, 25067908, 31754524, 41661514, 42386748, 51755988, 54296298

Offset: 1

Vladimir Shevelev, Jun 15 2008

nonn

Cf. A002326, A141229, A001122, A006694.

r[n_] := EulerPhi[n]/MultiplicativeOrder[2, n]; d[n_] := DivisorSum[n, r[#] &]; f[n_] := (m = MultiplicativeOrder[2, n])*d[n] - m + 1; MultiplicativeOrder[2, #] & /@  Select[Range[10^5], CompositeQ[#] && Total@(r /@ Divisors[#]) - 1 == 3 &] (* Amiram Eldar, Sep 12 2019 *)

a(4) corrected and more terms added by Amiram Eldar, Sep 12 2019

A140320 a(n) = A137576((3^n-1)/2).

Original entry on oeis.org

1, 3, 13, 55, 217, 811, 2917, 10207, 34993, 118099, 393661, 1299079, 4251529, 13817467, 44641045, 143489071, 459165025, 1463588515, 4649045869, 14721978583, 46490458681, 146444944843, 460255540933, 1443528742015, 4518872583697, 14121476824051, 44059007691037, 137260754729767

Offset: 0

Vladimir Shevelev, May 26 2008

nonn

Conjecture. a(n) = 2n*3^(n-1)+1.
If conjecture is true then limsup(A137576(n)/n)=infinity while liminf(A137576(n)/n)=2 with a realization on primes.
a(n) is also the number of edges in the graph generated from the n-dimensional hypercube (plus 1) in the following manner: connect all (d + 1)-dimensional faces to the d faces that are incident. Each d-dimensional face should be incident on (n - d) (d + 1)-dimensional faces. [Roy Liu (royliu(AT)cs.ucsd.edu), Jul 26 2010]

Wikipedia, Hypercube

Cf. A037576, A002326, A006694, A025192.

a137576(n) = my(t); sumdiv(2*n+1, d, eulerphi(d)/(t=znorder(Mod(2, d))))*t-t+1;
a(n) = a137576((3^n-1)/2); \\ Michel Marcus, Dec 18 2018

Sum_{m = 0}^{n} 2^(n - m) * binomial(n,m) is the number of m-dimensional faces in the n-dimensional hypercube. Consequently, Sum_{m = 0..n} (n - m) * 2^(n - m) * binomial(n,m) gives the number of incidence edges, which yields said sequence minus 1. The recurrence relation is: a(n) = 3 * a(n - 1) + 2 * 3^(n - 1) - 2. [Roy Liu (royliu(AT)cs.ucsd.edu), Jul 26 2010]

Empirical G.f.: (1-4*x+7*x^2)/(1-7*x+15*x^2-9*x^3). [Colin Barker, Jan 09 2012]

More terms from Michel Marcus, Dec 18 2018

A220019 Number of cyclotomic cosets of 7 mod 10^n.

Original entry on oeis.org

4, 27, 93, 265, 685, 1265, 2005, 2905, 3965, 5185, 6565, 8105, 9805, 11665, 13685, 15865, 18205, 20705, 23365, 26185, 29165, 32305, 35605, 39065, 42685, 46465, 50405, 54505, 58765, 63185, 67765, 72505, 77405, 82465, 87685, 93065, 98605, 104305, 110165, 116185, 122365, 128705, 135205, 141865, 148685

Offset: 1

V. Raman, Jan 27 2013

			a(2) = 27 because there are 27 cyclotomic cosets of 7 mod 100:
{1, 7, 49, 43}
{2, 14, 98, 86}
{3, 21, 47, 29}
{4, 28, 96, 72}
{5, 35, 45, 15}
{6, 42, 94, 58}
{8, 56, 92, 44}
{9, 63, 41, 87}
{10, 70, 90, 30}
{11, 77, 39, 73}
{12, 84, 88, 16}
{13, 91, 37, 59}
{17, 19, 33, 31}
{18, 26, 82, 74}
{20, 40, 80, 60}
{22, 54, 78, 46}
{23, 61, 27, 89}
{24, 68, 76, 32}
{25, 75}
{34, 38, 66, 62}
{36, 52, 64, 48}
{50}
{51, 57, 99, 93}
{53, 71, 97, 79}
{55, 85, 95, 65}
{67, 69, 83, 81}
{0}

Index entries for linear recurrences with constant coefficients, signature (3, -3, 1).

Cf. A006694, A220468.

a[n_] := DivisorSum[10^n, EulerPhi[#] / MultiplicativeOrder[7, #] & ]; Array[a, 50] (* Jean-François Alcover, Dec 18 2015 *)

for(n=1,50,print1(sumdiv(10^n, d, eulerphi(d)/znorder(Mod(7, d)))", "))

Empirical G.f.: x*(88*x^5-142*x^4-63*x^3-24*x^2-15*x-4) / (x-1)^3. [Colin Barker, Feb 03 2013]

Conjecture: a(n) = 5*(16*n^2-60*n+37) for n>3. a(n) = 3*a(n-1)-3*a(n-2)+a(n-3) for n>6. [Colin Barker, Apr 14 2013]

A220020 Number of cyclotomic cosets of 9 mod 10^n.

Original entry on oeis.org

6, 20, 56, 140, 256, 404, 584, 796, 1040, 1316, 1624, 1964, 2336, 2740, 3176, 3644, 4144, 4676, 5240, 5836, 6464, 7124, 7816, 8540, 9296, 10084, 10904, 11756, 12640, 13556, 14504, 15484, 16496, 17540, 18616, 19724, 20864, 22036, 23240, 24476, 25744, 27044, 28376, 29740, 31136, 32564, 34024, 35516, 37040, 38596

Offset: 1

V. Raman, Jan 27 2013

			a(2) = 20 because there are 20 cyclotomic cosets of 9 mod 100:
{1, 9, 81, 29, 61, 49, 41, 69, 21, 89}
{3, 27, 43, 87, 83, 47, 23, 7, 63, 67}
{11, 99, 91, 19, 71, 39, 51, 59, 31, 79}
{13, 17, 53, 77, 93, 37, 33, 97, 73, 57}
{2, 18, 62, 58, 22, 98, 82, 38, 42, 78}
{4, 36, 24, 16, 44, 96, 64, 76, 84, 56}
{6, 54, 86, 74, 66, 94, 46, 14, 26, 34}
{8, 72, 48, 32, 88, 92, 28, 52, 68, 12}
{10, 90}
{30, 70}
{20, 80}
{40, 60}
{50}
{5, 45}
{15, 35}
{55, 95}
{65, 85}
{25}
{75}
{0}

Index entries for linear recurrences with constant coefficients, signature (3, -3, 1).

Cf. A006694, A220468.

a[n_] := DivisorSum[10^n, EulerPhi[#]/MultiplicativeOrder[9, #]&]; Array[a, 50] (* Jean-François Alcover, Dec 10 2015, adapted from PARI *)
LinearRecurrence[{3,-3,1},{6,20,56,140,256},50] (* Harvey P. Dale, Jul 12 2025 *)

for(n=1,50,print1(sumdiv(10^n, d, eulerphi(d)/znorder(Mod(9, d)))", "))

Conjecture: a(n) = 4*(4*n^2-7*n-1) for n>2. a(n) = 3*a(n-1)-3*a(n-2)+a(n-3) for n>5. G.f.: 2*x*(8*x^4-13*x^3-7*x^2-x-3) / (x-1)^3. - Colin Barker, Apr 13 2013

A220021 Number of cyclotomic cosets of 11 mod 10^n.

Original entry on oeis.org

10, 27, 65, 119, 189, 275, 377, 495, 629, 779, 945, 1127, 1325, 1539, 1769, 2015, 2277, 2555, 2849, 3159, 3485, 3827, 4185, 4559, 4949, 5355, 5777, 6215, 6669, 7139, 7625, 8127, 8645, 9179, 9729, 10295, 10877, 11475, 12089, 12719, 13365, 14027, 14705, 15399, 16109, 16835, 17577, 18335, 19109, 19899

Offset: 1

V. Raman, Jan 27 2013

How is this related to A181890? - R. J. Mathar, Apr 11 2013

			a(2) = 27 because there are 27 cyclotomic cosets of 11 mod 100:
{1, 11, 21, 31, 41, 51, 61, 71, 81, 91}
{3, 33, 63, 93, 23, 53, 83, 13, 43, 73}
{7, 77, 47, 17, 87, 57, 27, 97, 67, 37}
{9, 99, 89, 79, 69, 59, 49, 39, 29, 19}
{2, 22, 42, 62, 82}
{12, 32, 52, 72, 92}
{4, 44, 84, 24, 64}
{14, 54, 94, 34, 74}
{6, 66, 26, 86, 46}
{16, 76, 36, 96, 56}
{8, 88, 68, 48, 28}
{18, 98, 78, 58, 38}
{5, 55}
{15, 65}
{25, 75}
{35, 85}
{45, 95}
{0}
{10}
{20}
{30}
{40}
{50}
{60}
{70}
{80}
{90}

Index entries for linear recurrences with constant coefficients, signature (3, -3, 1).

Cf. A006694, A220468.

a[n_] := DivisorSum[10^n, EulerPhi[#] / MultiplicativeOrder[11, #] &]; Array[a, 50] (* Jean-François Alcover, Dec 18 2015 *)

for(n=1,50,print1(sumdiv(10^n, d, eulerphi(d)/znorder(Mod(11, d)))", "))

Conjecture: a(n) = 8*n^2-2*n-1 for n>1. a(n) = 3*a(n-1)-3*a(n-2)+a(n-3) for n>4. G.f.: x*(5*x^3-14*x^2+3*x-10) / (x-1)^3. - Colin Barker, Apr 13 2013

cp's OEIS Frontend

A221855 Number of cyclotomic cosets of 13 mod 10^n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A333468 Length of the largest disjoint cycle of the permutation that results from the composition of first n circular shifts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A366494 a(n) is the number of cycles of the map f(x) = 10*x mod (10*n - 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

Python

A139042 Composite numbers c for which A064287((c-1)/2)=1.

Views

Author

Keywords

Comments

Crossrefs

Extensions

A140197 A137576((k-1)/2) for composite numbers k from A141229.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Extensions

A140198 A002326((k-1)/2) for composite numbers k from A141229.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Extensions

A140320 a(n) = A137576((3^n-1)/2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Extensions

A220019 Number of cyclotomic cosets of 7 mod 10^n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A366494 a(n) is the number of cycles of the map f(x) = 10x mod (10n - 1).