A357006 -id:A357006 - cp's OEIS frontend

A357000 Number of non-isomorphic cyclic Haar graphs on 2*n nodes.

1, 2, 3, 5, 5, 12, 9, 22, 21, 44, 29, 157, 73, 244, 367, 649, 521, 2624, 1609, 7385, 8867, 19400, 16769, 92529, 67553, 216274, 277191, 815557, 662369, 4500266, 2311469

Offset: 1

Pontus von Brömssen, Sep 08 2022

The first value of n for which a(n) < A002729(n) - 1 is n = 8. This is because the first counterexample to the bicirculant analog to Ádám's conjecture occurs for n = 8. In the terminology of Hladnik, Marušič, and Pisanski, the smallest integer pair (i,j) such that i and j are Haar equivalent (i.e., the cyclic Haar graphs with indices i and j are isomorphic) but not cyclically equivalent (see A357005) is (141,147). See also A357001 and A357002.

Terms a(1)-a(29) were found by generating the cyclic Haar graphs with indices in A333764, and filtering out isomorphic graphs using Brendan McKay's software nauty.

Milan Hladnik, Dragan Marušič, and Tomaž Pisanski, Cyclic Haar graphs, Discrete Mathematics 244 (2002), 137-152.
Eric Weisstein's World of Mathematics, Haar Graph

Cf. A002729, A008965, A049287, A091696, A137706, A291166, A333764, A339502, A357001, A357002, A357003, A357004, A357005, A357006.

a(n) is the number of terms k of A137706 in the interval 2^(n-1) <= k < 2^n.
a(n) is the number of fixed points k of A357004 in the interval 2^(n-1) <= k < 2^n.
a(n) <= A002729(n)-1 <= A091696(n) <= A008965(n).

a(30) from Eric W. Weisstein, Jun 27 2023

a(31) from Eric W. Weisstein, Jun 28 2023

A357005 Smallest k that is cyclically equivalent (see Comment for definition) to n.

Original entry on oeis.org

1, 2, 3, 4, 5, 5, 7, 8, 9, 10, 11, 9, 11, 11, 15, 16, 17, 17, 19, 17, 19, 19, 23, 17, 19, 19, 23, 19, 23, 23, 31, 32, 33, 34, 35, 36, 37, 37, 39, 34, 37, 42, 43, 37, 45, 43, 47, 33, 35, 37, 39, 37, 43, 45, 47, 35, 39, 43, 47, 39, 47, 47, 63, 64, 65, 65, 67, 65

Offset: 1

Pontus von Brömssen, Sep 08 2022

nonn

Two positive integers k and n are cyclically equivalent (as defined by Hladnik, Marušič, and Pisanski, 2002) if they have the same number m of binary digits, and there exist integers s and t such that gcd(s,m) = 1 and the map x -> s*x+t mod m maps the set of exponents of 2 occurring in the binary expansion of n bijectively to the corresponding set for k. (In particular, A000120(k) = A000120(n).) For example, k = 17 = 2^0 + 2^4 and n = 18 = 2^1 + 2^4 are cyclically equivalent, because the map x -> 2*x+2 mod 5 maps {1,4} to {0,4}.
The fixed points are the terms of A357006.
The number of fixed points n in the interval 2^(m-1) <= n < 2^m equals A002729(m)-1.

Pontus von Brömssen, Table of n, a(n) for n = 1..10000
Milan Hladnik, Dragan Marušič, and Tomaž Pisanski, Cyclic Haar graphs, Discrete Mathematics 244 (2002), 137-152.

Cf. A000120, A002729, A163382, A267508, A357004, A357006.

from math import gcd
def A357005(n):
    p=[int(d) for d in format(n,'b')]
    m=len(p)
    p0=min([p[(k*i+j)%m] for i in range(m)] for k in range(1,m+1) if gcd(k,m)==1 for j in range(m) if p[j])
    return sum(p0[i]*2**(m-1-i) for i in range(m))

a(a(n)) = a(n).
a(n) = A357004(n) for n <= 146, but a(147) = 147 > 141 = A357004(147).
A357004(n) <= a(n) <= A163382(n).

cp's OEIS Frontend

A357000 Number of non-isomorphic cyclic Haar graphs on 2*n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions