|
|
A000031
|
|
Number of n-bead necklaces with 2 colors when turning over is not allowed; also number of output sequences from a simple n-stage cycling shift register; also number of binary irreducible polynomials whose degree divides n.
(history;
published version)
|
|
|
#213 by R. J. Mathar at Sun Jan 28 08:03:05 EST 2024
|
|
|
|
#212 by R. J. Mathar at Sun Jan 28 08:02:43 EST 2024
|
| FORMULA
|
a(n) = (1/n)*Sum_{ d divides n } phi(d)*2^(n/d), ) = A053635(n)/n, where phi is A000010.
|
| STATUS
|
approved
editing
|
|
|
|
#211 by Joerg Arndt at Thu Nov 17 05:11:17 EST 2022
|
|
|
|
#210 by Michel Marcus at Thu Nov 17 01:25:57 EST 2022
|
|
|
|
#209 by Jon E. Schoenfield at Wed Nov 16 22:53:53 EST 2022
|
|
|
|
#208 by Jon E. Schoenfield at Wed Nov 16 22:53:50 EST 2022
|
| EXAMPLE
|
The analogous shift register sequences are {000..., 001001..., 011011..., 111...} and {000..., 00010001..., 00110011..., 0101..., 01110111..., 111... }....}.
|
| STATUS
|
proposed
editing
|
|
|
|
#207 by Chai Wah Wu at Wed Nov 16 19:59:18 EST 2022
|
|
|
|
#206 by Chai Wah Wu at Wed Nov 16 19:59:04 EST 2022
|
| PROG
|
(Python)
from sympy import totient, divisors
def A000031(n): return sum(totient(d)*(1<<n//d) for d in divisors(n, generator=True))//n if n else 1 # Chai Wah Wu, Nov 16 2022
|
| STATUS
|
approved
editing
|
|
|
|
#205 by Michael De Vlieger at Sat Apr 30 10:36:52 EDT 2022
|
|
|
|
#204 by Jon E. Schoenfield at Sat Apr 30 10:36:05 EDT 2022
|
|
|
|