A180026 -id:A180026 - cp's OEIS frontend

A003042 Number of directed Hamiltonian cycles (or Gray codes) on n-cube.

Original entry on oeis.org

1, 2, 12, 2688, 1813091520, 71676427445141767741440

Offset: 1

N. J. A. Sloane

Finding a(6) is Problem 43 in the Knuth reference.

Martin Gardner, Knotted Doughnuts and Other Mathematical Entertainments. Freeman, NY, 1986, p. 24.
Donald E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, (to appear), section 7.2.1.1.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Michel Deza and Roman Shklyar, Enumeration of Hamiltonian Cycles in 6-cube, arXiv:1003.4391 [cs.DM], 2010. [There may be errors - see Haanpaa and Ostergard, 2012]
Harri Haanpaa and Patric R. J. Östergård, Counting Hamiltonian cycles in bipartite graphs, Math. Comp. 83 (2014), 979-995.
John Jungck, Genetic Codes as Codes: Towards a Theoretical Basis for Bioinformatics, International Symposium on Mathematical and Computational Biology (BIOMAT 2008), see p. 19.
Jerry Silverman, Virgil E. Vickers, and John L. Sampson, Statistical estimates of the n-bit Gray codes by restricted random generation of permutations of 1 to 2^n, IEEE Trans. Inform. Theory 29 (1983), no. 6, 894-901.
Vladimir Shevelev, Combinatorial minors of matrix functions and their applications, arXiv:1105.3154 [math.CO], 2011-2014.
Vladimir Shevelev, Combinatorial minors of matrix functions and their applications
Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Eric Weisstein's World of Mathematics, Hypercube Graph

Equals A006069 divided by 2^n.

Cf. A006070, A091299, A003043, A091302, A066037, A159344, A180026.

a(n) = 2 * A066037(n).

a(6) from Michel Deza, Mar 28 2010

a(6) corrected by Haanpaa and Östergård, 2012. - N. J. A. Sloane, Sep 06 2012

A179926 Number of permutations of the divisors of n of the form d_1=n, d_2, d_3, ..., d_tau(n) such that d_(i+1)/d_i is a prime or 1/prime for all i.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 1, 2, 2, 1, 1, 3, 1, 3, 2, 2, 1, 4, 1, 2, 1, 3, 1, 18, 1, 1, 2, 2, 2, 8, 1, 2, 2, 4, 1, 18, 1, 3, 3, 2, 1, 5, 1, 3, 2, 3, 1, 4, 2, 4, 2, 2, 1, 106, 1, 2, 3, 1, 2, 18, 1, 3, 2, 18, 1, 17, 1, 2, 3, 3, 2, 18, 1, 5, 1, 2, 1, 106, 2, 2, 2, 4, 1, 106, 2, 3, 2, 2, 2, 6, 1, 3, 3, 8, 1, 18, 1, 4, 18, 2, 1, 17, 1, 18, 2, 5, 1, 18, 2, 3, 3, 2, 2, 572

Offset: 1

Vladimir Shevelev, Aug 02 2010

nonn

In view of formulas given below, there are many common first terms with A001221. Note that, for n >= 1, a(n) is positive; it is function of exponents of prime power factorization of n only; moreover, it is invariant with respect to permutations of them.
An equivalent multiset formulation of the problem: for a given finite multiset A, we should, beginning with A, to get all submultisets of A, if, by every step, we remove or join 1 element. How many ways are there to do this?
Via Seqfan Discussion List (Aug 03 2010), Alois P. Heinz proved that every subsequence of the form a(p), a(p*q), a(p*q*r), ..., where p, q, r, ... are distinct primes, coincides with A003043. - Vladimir Shevelev, Aug 09 2010
The parity (odd or even) of bigomega(d_i) in a permutation of divisors of n alternates. - David A. Corneth, Nov 25 2017
Equivalently, the number of Hamiltonian paths in a graph with vertices corresponding to the divisors of n and edges connecting divisors that differ by a prime with the path starting on the vertex associated with 1. - Andrew Howroyd, Oct 26 2019

			a(12)=3:
[12, 6, 3, 1, 2, 4]
[12, 4, 2, 6, 3, 1]
[12, 4, 2, 1, 3, 6]
a(45)=3:
[45, 15, 5, 1, 3, 9]
[45, 9, 3, 15, 5, 1]
[45, 9, 3, 1, 5, 15]

Alois P. Heinz, Table of n, a(n) for n = 1..1259 (first 719 terms from David A. Corneth)
David A. Corneth, The permutations of divisors for a(60) ordered by their last element.
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).
Index entries for sequences computed from exponents in factorization of n

Cf. A000005, A001221, A180026, A003043, A003042. - Vladimir Shevelev, Aug 09 2010
See A173675 for another version.
Cf. A119842, A295785.

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:= n-> (s-> b(s minus {n}, n))(numtheory[divisors](n)):
seq(a(n), n=1..100);  # Alois P. Heinz, Nov 26 2017

q[i_, j_] := PrimeQ[i/j];
b[s_, l_] := b[s, l] = If[s == {}, 1, Sum[If[q[l, j] || q[j, l], b[s  ~Complement~ {j}, j], 0], {j, s}]];
a[n_] := Function[s, b[s ~Complement~ {n}, n]][Divisors[n]];
Array[a, 120] (* Jean-François Alcover, Dec 13 2017, after Alois P. Heinz *)

a(n) = {my(f = factor(n), l = List(), chain = List()); res = 0; forvec(x = vector(#f~, i, [0, f[i, 2]]), listput(l, x)); listput(chain, l[#l]); listpop(l, #l); iterate(chain, l); res}
iterate(c, l) = {if(#l == 1, if(vecsum(abs(c[#c] - l[1])) == 1, res++), my(cc, cl);
for(i = 1, #l, if(vecsum(abs(c[#c] - l[i])) == 1, cc = c; cl = l; listput(cc, l[i]); listpop(cl, i); iterate(cc, cl))))}
first(n) = {my(res = vector(n), m = Map()); res[1] = 1; for(i = 2, n, cn = a046523(i); if(cn == i, mapput(m, i, a(i))); res[i] = mapget(m, cn)); res}
a046523(n)=my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f,(p=nextprime(p+1))^f[i]) \\ (a046523 from Charles R Greathouse IV), David A. Corneth, Nov 24 2017

a(p^k)=1, a(p^k*q)=k+1, a(p^2*q^2)=8, a(p^2*q^3)=17, a(pqr)=18, a(p^2*q*r)=106, a(p^3*q*r)=572, etc. (here p,q,r are distinct primes, k >= 0).

Corrected by D. S. McNeil and Alois P. Heinz and extended by Alois P. Heinz from a(46) via the Seqfan Discussion List (Aug 02 2010)

A180253 Call two divisors of n adjacent if the larger is a prime times the smaller. a(n) is the sum of elements of all pairs of adjacent divisors of n.

Original entry on oeis.org

0, 3, 4, 9, 6, 24, 8, 21, 16, 36, 12, 64, 14, 48, 48, 45, 18, 87, 20, 96, 64, 72, 24, 144, 36, 84, 52, 128, 30, 216, 32, 93, 96, 108, 96, 229, 38, 120, 112, 216, 42, 288, 44, 192, 174, 144, 48, 304, 64, 201, 144, 224, 54, 276, 144, 288, 160, 180, 60, 552, 62, 192, 232, 189

Offset: 1

Vladimir Shevelev, Aug 20 2010

The pairs of adjacent divisors of n are counted in A062799(n).

For each divisor d of n we can check in how many pairs it occurs. For each prime divisor p of n, see the exponent of p in the factorization of d. If it's positive (p|d) then it occurs once more. If d*p doesn't divide n, add one to the frequency as well. - David A. Corneth, Dec 17 2018

			a(4) = (1 + 2) + (2 + 4) = 9.
a(120) = a(3*5*2^3) = 4*6*(3*8 + 4*4 + 4*2 + 3) = 1224.

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

Cf. A001221, A062799, A069359, A179926, A180026, A323599, A328260, A329354, A329375.

divisorSumPrime[n_] := DivisorSum[n, 1+1/# &, PrimeQ[#] &]; a[n_] := DivisorSum[n, #*divisorSumPrime[#]& ]; Array[a, 70] (* Amiram Eldar, Dec 17 2018 *)

a(n) = sumdiv(n, d, d*sumdiv(d, p, isprime(p)*(1+1/p))); \\ Michel Marcus, Dec 17 2018

a(n) = my(f = factor(n), res = 0); fordiv(n, d, for(i = 1, #f~, v = valuation(d, f[i, 1]); res+=(d * ((v > 0) + (v < f[i, 2]))))); res \\ David A. Corneth, Dec 17 2018

a(n) = Sum_{d|n} d*Sum_{p|d} (1 + 1/p) where p is restricted to primes.
a(n) = Sum_{d|n} A069359(d) + Sum_{d|n} d*A001221(d).
a(n) = A323599(n) + A329354(n) = A323599(n) + A328260(n) + A329375(n). - Antti Karttunen, Nov 15 2019
a(p^k) = (p^k - 1)*(p + 1)/(p - 1).
a(p_1*p_2*...*p_m) = m*(p_1 + 1)*(p_2 + 1)*...*(p_m + 1).
a(p*q^k) = (p + 1)*(2*q^k + 3*q^(k - 1) + 3*q^(k - 2) + ... + 3*q + 2).
a(p*q*r^k) = (p + 1)*(q + 1)*(3*r^k + 4*r^(k - 1) + 4*r^(k - 2) + ... + 4*r + 3) and similar for a larger number of distinct prime factors of n.

Definition rephrased, entries checked, one example added. - R. J. Mathar, Oct 25 2010

cp's OEIS Frontend

A003042 Number of directed Hamiltonian cycles (or Gray codes) on n-cube.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A179926 Number of permutations of the divisors of n of the form d_1=n, d_2, d_3, ..., d_tau(n) such that d_(i+1)/d_i is a prime or 1/prime for all i.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A180253 Call two divisors of n adjacent if the larger is a prime times the smaller. a(n) is the sum of elements of all pairs of adjacent divisors of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions