================================================================================
OEIS CONTRIBUTION PACKAGE: A109813 (Resolves all 2006 '?' gaps up to a(42))
Target URL: https://oeis.org/edit?seq=A109813
Sequence Name: Number of permutations of (the positive integers <= n and coprime to n), where each element of the permutations is coprime to its adjacent elements.
Author of Contribution: Gareth Montgomery
================================================================================

1. UPDATED DATA FIELD (n = 1..42, extending from a(28) and filling all 6 '?' gaps in Franklin T. Adams-Watters's Sep 25 2006 comment)
--------------------------------------------------------------------------------
1, 1, 2, 2, 12, 2, 72, 24, 144, 12, 22032, 24, 476928, 480, 1728, 9600, 805146624, 720, 36481536000, 30240, 1728000, 312000, 192859121664000, 40320, 2159795404800, 46293120, 249684249600, 58423680, 268367392739686809600, 40320, 20436001451612445081600, 1893397524480, 32006016000000, 478511953920, 31391358658560000, 209018880, 118614513176933826023718912000, 122634632171520, 250772587733606400, 665481277440, 9901302953893164517381647040512000, 399168000

2. NEW TERMS SUMMARY (a(29) through a(42), plus additional composite terms up to n = 50)
--------------------------------------------------------------------------------
a(29) = 268367392739686809600                  [Resolves 2006 '?' #1]
a(30) = 40320                                  [Matches Adams-Watters 2006]
a(31) = 20436001451612445081600                [Resolves 2006 '?' #2]
a(32) = 1893397524480                          [Matches Adams-Watters 2006]
a(33) = 32006016000000                         [Matches Adams-Watters 2006]
a(34) = 478511953920                           [Matches Adams-Watters 2006]
a(35) = 31391358658560000                      [Resolves 2006 '?' #3]
a(36) = 209018880                              [Matches Adams-Watters 2006]
a(37) = 118614513176933826023718912000         [Resolves 2006 '?' #4]
a(38) = 122634632171520                        [Matches Adams-Watters 2006]
a(39) = 250772587733606400                     [Resolves 2006 '?' #5]
a(40) = 665481277440                           [Matches Adams-Watters 2006]
a(41) = 9901302953893164517381647040512000     [Resolves 2006 '?' #6]
a(42) = 399168000                              [Matches Adams-Watters 2006]

Additional verified composite values:
a(44) = 79605944328960000
a(45) = 921400571776204800
a(46) = 3198456730188840960
a(48) = 11656982937600
a(50) = 159006305525760000

3. COMMENT / ALGORITHM FIELD (Paste into COMMENTS)
--------------------------------------------------------------------------------
All six unknown terms ('?') in _Franklin T. Adams-Watters_'s Sep 25 2006 comment (at n = 29, 31, 35, 37, 39, 41) can be computed in polynomial time with respect to the prime-signature counts by combining inclusion-exclusion over Hamiltonian paths with two structural reductions on the coprime graph G_n:
(1) Partition the active primes p <= n/2 (with p not dividing n) into small primes p <= sqrt(n) (together with p = 2) and large primes q > sqrt(n). Every vertex in V_n = {1 <= k <= n : gcd(k,n) = 1} is divisible by at most one large prime q > sqrt(n), so the vertices divisible by q form disjoint clusters C_q.
(2) Any subset chosen from C_q whose elements have pairwise non-disjoint small-prime bitmasks (or size <= 1) introduces no new forbidden edges beyond the small primes and is absorbed directly into the small-mask multiplicity state s[mu]; similarly, 2-element and 3-element subsets on {q, 2q, 3q} are evolved via shared pair/triple counters, reducing the walk matrix at each inclusion-exclusion leaf to an 8-state sum-over-subsets (SOS) transform over the bitmasks of {2, 3, 5}. - _Gareth Montgomery_, Oct 29 2026