divrep/README-A006558 at master · hvds/divrep · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
https://oeis.org/A006558
Start of first run of n consecutive integers with same number of divisors.

Values up to a(10) are known, beyond that we have only upper bounds
the first of which is that a(11) <= D(24,11) = 17707503256664346.
We can use the code and knowledge from investigations of A292580 to
determine what tau(a(n)) are possible candidates to reduce the bound.

1) For n > 7, we know that tau(a(n)) must be a multiple of 12.

2) From A002182(n) we find that a(n) < D(24,11) -> tau(a(n)) <= 46080,
giving us 46080/12 = 3840 initial candidates.

3) Running './pcoul -x17707503256664346 $v 1' for each candidate $v reduces
the pool to 570 candidates. Repeating for k=2 further reduces it to 68, but
required a couple of days of manually tweaking pcoul options for different
cases to get results. This is not a sustainable approach, but gives us
an idea what to expect.

4) We can make an initial pass at filtering candidates more efficiently,
by considering just the product of the values - if we require k (almost)
pairwise coprime values v_i: tau(v_i) = t, then setting V = \prod{v_i}
gives us (roughly) \tau{V} = t^k.

Making this more rigorous, let p^e be the highest power of p dividing
any of the v_i. Then at most floor((k-1)/p^f) - floor((k-1)/p^{f+1})
additional values will be divisible by p^f. Variations are possible in
which a lower power replaces a higher power, but if we consider only
possible values of V without further constraints, those variations can
only lead to higher V.

The program 'filter' sets k in sequence to 1, 2, ... n to successively
prune the candidate list, giving counts as follows:

n=8: 560 (initial), 181, 53, 30, 21, 18, 14, 12, 11 (2.03s)
n=9: 640, 197, 59, 33, 24, 18, 15, 12, 12, 11 (2.84s)
n=10: 2688, 461, 129, 71, 46, 39, 29, 28, 23, 19, 18 (13.11s)
n=11: 3840, 570, 156, 85, 59, 45, 35, 29, 27, 25, 22, 18 (25.17s)
n=12: 10752, 991, 259, 137, 91, 68, 55, 45, 42, 36, 34, 30, 27 (86.01s)
n=13: 20736, 1365, 345, 182, 121, 92, 69, 60, 51, 45, 42, 40, 36, 35 (266.76s)
n=14: 163840, 3644, 848, 421, 265, 199, 154, 131, 109, 98, 87, 82, 72, 70, 61 (4103.32s)
n=15: 737280, 7287, 1591, 760, 476, 347, 264, 222, 184, 165, 149, 135, 120
  crashed 'free(): invalid pointer' at 13:2520 after 3.5h, to be retried

And resulting candidate lists so:
n=8: 12 24 36 48 60 72 84 96 108 120 144
n=9: 12 24 36 48 60 72 84 96 108 120 144
n=10: 12 24 36 48 60 72 84 96 108 120 144 168 180 192 216 240 288 384
n=11: 12 24 36 48 60 72 84 96 108 120 144 168 180 192 216 240 288 384
n=12: 12 24 36 48 60 72 84 96 108 120 132 144 168 180 192 216 240 252 288
  300 324 336 360 384 432 480 576
n=13: 12 24 36 48 60 72 84 96 108 120 132 144 156 168 180 192 216 240 252
  264 288 300 324 336 360 384 432 480 504 540 576 648 720 768 864
n=14: 12 24 36 48 60 72 84 96 108 120 132 144 156 168 180 192 204 216 240
  252 264 288 300 312 324 336 360 384 396 420 432 468 480 504 528 540 576
  600 648 672 720 756 768 792 840 864 900 960 972 1008 1080 1152 1200 1296
  1344 1440 1536 1728 1920 2304 3072

5) We can now cross-check against known values (or known constraints) for
A292580, to confirm known values of a(n) = A6558(n) and provide a list of
remaining tau() values that need checking for those not yet known.

n=8: a(n) = 1043710445721 = D(24,8);
  candidates: 12 24 36 48 60 72 84 96 108 120 144
    D( 12, 8) = 15724736975643
    D( 24, 8) = 1043710445721
    D( 36, 6) = 2595541876334839548
    D( 48, 8) = 15638027885721
    D( 60, 5) = 23459236100384066979372
    D( 72, 5) = 49301742601472
    D( 84, 5) = 260345705241605884190608109372
    D( 96, 7) = 274094359128666
    D(108, 4) = 1702925212106987099
    D(120, 5) = 282370531944978198124
    D(144, 4) = 42719184210175
  thus confirming a(8) = D(24,8)

n=9: a(n) = 2197379769820 = D(24,9):
  candidates: 12 24 36 48 60 72 84 96 108 120 144
    D( 12, 9) = 15724736975643
    D( 24, 9) = 2197379769820
    D( 36, 6) = 2595541876334839548
    D( 48, 9) = 638685576505820
    D( 60, 5) = 23459236100384066979372
    D( 72, 5) = 49301742601472
    D( 84, 5) = 260345705241605884190608109372
    D( 96, 7) = 274094359128666
    D(108, 4) = 1702925212106987099
    D(120, 5) = 282370531944978198124
    D(144, 4) = 42719184210175
  thus confirming a(9) = D(24,9)

n=10: a(n) = 2642166652554075 = D(24,10):
  candidates: 12 24 36 48 60 72 84 96 108 120 144 168 180 192 216 240 288 384
    D( 12, 10) = 2973879756088065948
    D( 24, 10) = 2642166652554075
    D( 36,  6) = 2595541876334839548
    D( 60,  5) = 23459236100384066979372
    D( 84,  5) = 260345705241605884190608109372
    D(108,  4) = 1702925212106987099
    D(120,  5) = 282370531944978198124
    D(144,  5) = 4825716276141824
    D(168,  4) = 3716387640038758328125
    D(180,  3) = 52324903172877775
    D(240,  4) = 324775227289518159
    D(288,  4) = 13870605765501693
    D(384,  4) = 12009062753274663
  this leaves candidates 48, 72, 96, 192, 216, so it asserts:
    D(i, 10) > 2642166652554075 for i in { 48, 72, 96, 192, 216 }

n=11: a(n) <= 17707503256664346 = D(24,11):
  candidates: 12 24 36 48 60 72 84 96 108 120 144 168 180 192 216 240 288 384
    D( 12, 11) = 9887353188984012120346
    D( 24, 11) = 17707503256664346
    D( 36,  6) = 2595541876334839548
    D( 60,  5) = 23459236100384066979372
    D( 84,  5) = 260345705241605884190608109372
    D(108,  4) = 1702925212106987099
    D(120,  5) = 282370531944978198124
    D(144,  6) > 17707503256664346
    D(168,  4) = 3716387640038758328125
    D(180,  3) = 52324903172877775
    D(216,  4) > 17707503256664346
    D(240,  4) = 324775227289518159
    D(288,  5) > 17707503256664346
    D(384,  5) > 17707503256664346
  this leaves candidates 48, 72, 96, 192, to be checked

n=12: a(n) <= 3842083249515874843 >= D(24,11)
  candidates: 12 24 36 48 60 72 84 96 108 120 132 144 168 180 192 216 240
        252 288 300 324 336 360 384 432 480 576
    D( 12, 12) = 120402988681658048433948
    D( 24, 12) <= 3842083249515874843
    D( 60,  5) = 23459236100384066979372
    D( 84,  5) = 260345705241605884190608109372
    D(120,  5) = 282370531944978198124
    D(132,  4) = 63013800726079188209351787109373
    D(168,  4) = 3716387640038758328125
    D(252,  3) = 23818007791493890623
    D(300,  3) = 7809924590411391890000
    D(324,  3) = 103148643381388141823
  this leaves candidates 24, 36, 48, 72, 96, 108, 144, 180, 192, 216, 240,
    288, 336, 360, 384, 432, 480, 576 to be checked