A284673 -id:A284673 - cp's OEIS frontend

A091299 Number of (directed) Hamiltonian paths (or Gray codes) on the n-cube.

2, 8, 144, 91392, 187499658240

Offset: 1

N. J. A. Sloane, Feb 20 2004

More precisely, this is the number of ways of making a list of the 2^n nodes of the n-cube, with a distinguished starting position and a direction, such that each node is adjacent to the previous one. The final node may or may not be adjacent to the first.

			a(1) = 2: we have 1,2 or 2,1. a(2) = 8: label the nodes 1, 2, ..., 4. Then the 8 possibilities are 1,2,3,4; 1,3,4,2; 2,3,4,1; 2,1,4,3; etc.

M. Gardner, Knotted Doughnuts and Other Mathematical Entertainments. Freeman, NY, 1986, p. 24.

Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, Hypercube Graph

Equals A006069 + A006070. Divide by 2^n to get A003043.

Cf. A003042, A066037, A091302, A284673.

# A function that calculates A091299[n] from Janez Brank.
def CountGray(n):
    def Recurse(unused, lastVal, nextSet):
        count = 0
        for changedBit in range(0, min(nextSet + 1, n)):
            newVal = lastVal ^ (1 << changedBit)
            mask = 1 << newVal
            if unused & mask:
                if unused == mask:
                    count += 1
                else:
                    count += Recurse(
                        unused & ~mask, newVal, max(nextSet, changedBit + 1)
                    )
        return count
    count = Recurse((1 << (1 << n)) - 2, 0, 0)
    for i in range(1, n + 1):
        count *= 2 * i
    return max(1, count)
[CountGray(n) for n in range(1, 4)]

a(5) from Janez Brank (janez.brank(AT)ijs.si), Mar 02 2005

A173675 Let d_1, d_2, d_3, ..., d_tau(n) be the divisors of n; a(n) = number of permutations p of d_1, d_2, d_3, ..., d_tau(n) such that p_(i+1)/p_i is a prime or 1/prime for i = 1,2,...,tau(n)-1 and p_1 <= p_tau(n).

Original entry on oeis.org

1, 1, 1, 1, 1, 4, 1, 1, 1, 4, 1, 8, 1, 4, 4, 1, 1, 8, 1, 8, 4, 4, 1, 14, 1, 4, 1, 8, 1, 72, 1, 1, 4, 4, 4, 20, 1, 4, 4, 14, 1, 72, 1, 8, 8, 4, 1, 22, 1, 8, 4, 8, 1, 14, 4, 14, 4, 4, 1, 584, 1, 4, 8, 1, 4, 72, 1, 8, 4, 72, 1, 62, 1, 4, 8, 8, 4, 72, 1, 22, 1, 4

Offset: 1

N. J. A. Sloane, Nov 24 2010

nonn

Variant of A179926 in which the permutation of the divisors may start with any divisor but the first term may not be larger than the last term.
From Andrew Howroyd, Oct 26 2019: (Start)
Equivalently, the number of undirected Hamiltonian paths in a graph with vertices corresponding to the divisors of n and edges connecting divisors that differ by a prime.
a(n) depends only on the prime signature of n. See A295786. (End)

			a(1) = 1: [1].
a(2) = 1: [1,2].
a(6) = 4: [1,2,6,3], [1,3,6,2], [2,1,3,6], [3,1,2,6].
a(12) = 8: [1,2,4,12,6,3], [1,3,6,2,4,12], [1,3,6,12,4,2], [2,1,3,6,12,4], [3,1,2,4,12,6], [3,1,2,6,12,4], [4,2,1,3,6,12], [6,3,1,2,4,12].

Andrew Howroyd, Table of n, a(n) for n = 1..2048
V. Shevelev, Combinatorial minors of matrix functions and their applications, arXiv:1105.3154 [math.CO], 2011-2014.
V. Shevelev, Combinatorial minors of matrix functions and their applications, Zesz. Nauk. PS., Mat. Stosow., Zeszyt 4, pp. 5-16. (2014).
Robert G. Wilson v, Re: A combinatorial problem, SeqFan (Aug 02 2010)

Cf. A000005, A000040, A002110, A101296, A179926, A284673, A295786.

See A295557 for another version.

with(numtheory):
q:= (i, j)-> is(i/j, integer) and isprime(i/j):
b:= proc(s, l) option remember; `if`(s={}, 1, add(
     `if`(q(l, j) or q(j, l), b(s minus{j}, j), 0), j=s))
    end:
a:= proc(n) option remember; ((s-> add(b(s minus {j}, j),
       j=s))(divisors(n)))/`if`(n>1, 2, 1)
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Nov 26 2017

b[s_, l_] := b[s, l] = If[s == {}, 1, Sum[If[PrimeQ[l/j] || PrimeQ[j/l], b[s ~Complement~ {j}, j], 0], {j, s}]];
a[n_] := a[n] = Function[s, Sum[b[s ~Complement~ {j}, j], {j, s}]][ Divisors[n]] / If[n > 1, 2, 1];
Array[a, 100] (* Jean-François Alcover, Nov 28 2017, after Alois P. Heinz *)

From Andrew Howroyd, Oct 26 2019: (Start)
a(p^e) = 1 for prime p.
a(A002110(n)) = A284673(n).
a(n) = A295786(A101296(n)). (End)

Alois P. Heinz corrected and clarified the definition and provided more terms. - Nov 07 2014

A295786 a(n) = A173675(A025487(n)).

Original entry on oeis.org

1, 1, 1, 4, 1, 8, 1, 14, 72, 1, 20, 22, 584, 1, 62, 32, 4016, 1, 132, 16880, 44, 45696, 276, 24656, 1, 336, 413484, 58, 11323440, 1006, 140624, 1, 688, 9044404, 74, 2384871120, 3610, 2480304, 761960, 1, 35281856, 1578, 68984506112, 4324, 183901520, 92, 446907448224, 12010, 677849536, 3976704, 1, 2683205048, 3190, 93749829120

Offset: 1

David A. Corneth, Dec 25 2017

nonn

Terms in A173675 are only determined by their prime signature. A025487 gives the least positive integer having its prime signature. Combining these sequences removes a lot of duplicates making it somewhat easier to show terms.
a(54) = A284673(5) = 93749829120. - Andrew Howroyd, Oct 26 2019
Many terms from Kloczkowski & Jernigan's Table IV (which has A003752 as a column) show up in the Data section of this sequence. For the (partial) explanation of that, see Andrew Howroyd's comment in A173675. - Andrey Zabolotskiy, Aug 07 2023

David A. Corneth, Prime signatures for some k and the corresponding values for A173675(k).
A. Kloczkowski and R. L. Jernigan, Transfer matrix method for enumeration and generation of compact self-avoiding walks. II. Cubic lattice, J. Chem. Phys., 109 (1998), 5147-5159.

Cf. A025487, A173675.

Terms a(29) and beyond from Andrew Howroyd, Oct 26 2019

cp's OEIS Frontend

A091299 Number of (directed) Hamiltonian paths (or Gray codes) on the n-cube.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Python

Extensions

A173675 Let d_1, d_2, d_3, ..., d_tau(n) be the divisors of n; a(n) = number of permutations p of d_1, d_2, d_3, ..., d_tau(n) such that p_(i+1)/p_i is a prime or 1/prime for i = 1,2,...,tau(n)-1 and p_1 <= p_tau(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A295786 a(n) = A173675(A025487(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions