Sequence A100933: Two Distinct Representations as Product of Integers>1
This sequence, Sloane's A100933, consists of
numbers that can be expressed as a product of two or more consecutive
integers greater than 1, in two distinct ways.
120 = 2×3×4×5 = 4×5×6
210 = 5×6×7 = 14×15 720 = 2×3×4×5×6 = 8×9×10
5040 = 2×3×...×6×7 = 7×8×9×10
175560 = 19×20×21×22 = 55×56×57 17297280 = 8×9×...×13×14 = 63×64×65×66
19958400 = 3×4×...×10×11 = 5×6×...×11×12
259459200 = 5×6×...×12×13 = 8×9×...×14×15
20274183401472000 = 4×5×...×18×19 = 6×7×...×19×20
25852016738884976640000 = 2×3×...×22×23 = 5×6×...×23×24
368406749739154248105984000000
= 5×6×...×28×29 = 7×8×...×29×30
all values up to 1.0×1036 have been checked possibly one or more undiscovered values here
278771055109698392568083850445339597209600000000
= 6×7×...×40×41 = 8×9×...×41×42
possibly one or more undiscovered values here
36055954861352887137197787308347629783163600896000000000
= 19×20×...×53×54 = 23×24×...×56×57
possibly one or more undiscovered values here
17633893546747605452729306732731273554972668127013106614272000000000000
= 7×8×...×54×55 = 9×10×...×55×56
...
The numbers above can be viewed as belonging to two categories,
overlapping and nonoverlapping, based on whether the two products
of integers have any terms in common.
Most of the overlapping cases are fairly simple to find. 19958400 is
an example of this case. The full expansion of its two product
representations is:
The part in the middle, comprising most of the terms, is the same. One
has "3×4" at the beginning, the other has "12" at the end. Because
3×4=12, you can see that the equation is true without doing any
multiplication. There is an equation like this for every number that
is the product of 2 or more consecutive integers (Sloane's
A045619).
There are a few other overlap cases, similar to 259459200:
Here the "extra" portions on the left and right both have more than
one term. In this case, "5×6×7" is replaced with "14×15". In
cases like this, the overlap portion can be removed and the result is
a different, non-overlap solution. In this example, the nonoverlapping
solution is 210 = 5×6×7 = 14×15. Thus, there is one overlapping
solution for each non-overlapping solution:
Three of these are shown above, the other one is similar.
Source code
NOTE: This code uses a 128-bit integer data type, here referred to
as "s128". "s128_str" converts a 128-bit integer to a string. "s32" should
be a native integer type of 32 or 64 bits.
The first version shows the essential concepts behind the algorithm:
maintaining a linked list of candidates, always sorted in order,
and detecting matches when two consecutive values are equal.
void pr_term_A045619(s128 init, s32 len)
{
char ss[45];
s128 t;
s32 i;
t = init;
if (len < 5) {
for(i=0; i0) { printf("{x}"); }
s128_str(t, ss); printf("%s", ss);
t = t + 1;
}
} else {
s128_str(t, ss); printf("%s", ss);
printf("{x}...{x}");
t = t + ((s128) (len - 1));
s128_str(t, ss); printf("%s", ss);
}
}
/* Version of prop_5040 that works by always keeping the candidates
pre-computed and in sorted order; in addition the candidates are
characterized by run length rather than by initial term, which greatly
reduces the number of candidates at any moment. */
void prop_5040_b()
{
// 35 is the factorial root of 2^128
#define MAXCAND_p5040 35
s128 cand[MAXCAND_p5040]; // The multiplied-out value
s128 init[MAXCAND_p5040]; // Initial term
s32 len[MAXCAND_p5040]; // Number of terms in product
s32 next[MAXCAND_p5040];
s32 first, // index of item that is first in linked list
last, // index of item that is last in linked list
free; // index of next available free node
s128 nextfact, // next factorial to stick into the list
nf_root; // factorial-root of nextfact
s32 nf_len; // equals (nf_root - 1)
s128 k2, limit;
s128 lasthit, lh_init; s32 lh_len;
char ss[45];
time_t st;
s32 tc;
st = time(0); tc = 0;
k2 = 2;
// Set up the list to contain two items, 2x3 and 2x3x4
first = 0;
init[0] = 2; len[0] = 2; cand[0] = 2 * 3;
next[0] = 1;
init[1] = 2; len[1] = 3; cand[1] = 2 * 3 * 4;
next[1] = -1; last = 1; free = 2;
// The next item to add will be 2x3x4x5
nextfact = 2 * 3 * 4 * 5;
nf_root = 5;
nf_len = 4;
lasthit = 0;
limit = 1000000;
limit *= 1000000;
limit *= 1000000; // 15:8 16:26 17:87 18:283
limit *= 1000000; // 19:940
while(cand[first] < limit) {
if (cand[first] == lasthit) {
s128 t, ca;
s32 i, cal;
s128_str(cand[first], ss); printf("%s = ", ss);
ca = init[first]; cal = len[first];
if (lh_init < ca) {
t = ca; ca = lh_init; lh_init = t;
i = cal; cal = lh_len; lh_len = i;
}
pr_term_A045619(ca, cal);
printf(" = ");
pr_term_A045619(lh_init, lh_len);
printf("\n");
}
lasthit = cand[first];
lh_init = init[first];
lh_len = len[first];
}
// increment the candidate
{
s32 i;
s128 p, t;
init[first] += 1; p = t = init[first];
for(i=1; i cand[next[first]]) {
// re-sort
s32 mover, i;
// take it out of the list
mover = first;
first = next[first];
// Find the new spot
for(i=first;
(next[i] >= 0) && (cand[next[i]] < cand[mover]);
i=next[i]) { }
if ((i == first) && (cand[mover] < cand[i])) {
// insert back onto beginning
next[mover] = first;
first = mover;
} else if (i < 0) {
// stick on end
next[mover] = -1;
next[last] = mover;
last = mover;
} else {
// insert in middle
next[mover] = next[i];
next[i] = mover;
}
}
// Now check if first item in list is bigger than nextfact, if so we can
// insert a new item
if (cand[first] >= nextfact) {
s32 i;
// Add another element to the list
cand[free] = nextfact;
init[free] = 2;
len[free] = nf_len;
// insert to beginning
next[free] = first;
first = free;
free++;
// calculate the next nextfact
nf_root += 1;
nextfact *= nf_root;
nf_len++;
}
if (++tc >= 10000000)
s128_str(cand[first], ss);
printf(" (up to %s...)\r", ss); fflush(stdout);
tc = 0;
}
printf("...\n");
printf("used %d nodes; elapsed time: %d \n",
free, ((int) (time(0) - st)));
}
The second version adds an optimization: It calculates all candidates
that are of length 3 or more, and for each one calculates a single
length-2 candidate. This saves time by avoiding all the other length-2
candidates, which comprise nearly all the time spent by the above
version.
void prop_5040_c()
{
s128 cand[MAXCAND_p5040]; // The multiplied-out value
s128 init[MAXCAND_p5040]; // Initial term
s32 len[MAXCAND_p5040]; // Number of terms in product
s32 next[MAXCAND_p5040];
s32 first, // index of item that is first in linked list
last, // index of item that is last in linked list
free; // index of next available free node
s128 nextfact, // next factorial to stick into the list
nf_root; // factorial-root of nextfact
s32 nf_len; // equals (nf_root - 1)
s128 k2, limit;
char ss[45];
time_t st;
s32 tc;
s128 r2, o2, t2;
st = time(0); tc = 0;
k2 = 2;
// initialize the oblong candidate.
r2 = 4; o2 = r2 * (r2+1);
// Set up the list to contain two items, 2x3x4 and 2x3x4x5
first = 0;
init[0] = 2; len[0] = 3; cand[0] = 2 * 3 * 4;
next[0] = 1;
init[1] = 2; len[1] = 4; cand[1] = 2 * 3 * 4 * 5;
next[1] = -1; last = 1; free = 2;
// The next item to add will be 2x3x4x5x6
nextfact = 2 * 3 * 4 * 5 * 6;
nf_root = 6;
nf_len = 5;
limit = 1000000000; limit *= limit; limit *= limit; // 10^36
while(cand[first] < limit) {
// check for match with nearest 2-term candidate
t2 = (cand[first] - o2) / 2; // should optimize to >> 1
r2 = r2 + (t2 / r2);
o2 = r2 * (r2 + 1);
while (o2 > cand[first]) {
r2 -= 1;
o2 = r2 * (r2+1);
}
if (o2 == cand[first]) {
s128_str(o2, ss); printf("%s = ", ss);
pr_term_A045619(init[first], len[first]);
printf(" = ");
printf("%llu{x}%llu", (u64)r2, (u64)r2 + 1);
printf("\n");
}
if (cand[first] == cand[next[first]]) {
// we have found a solution
s32 m1, m2, t1;
m1 = first;
m2 = next[m1];
s128_str(cand[m1], ss); printf("%s = ", ss);
if (init[m2] < init[m1]) {
t1 = m1; m1 = m2; m2 = t1;
}
pr_term_A045619(init[m1], len[m1]);
printf(" = ");
pr_term_A045619(init[m2], len[m2]);
printf("\n");
}
// increment the candidate
{
s32 i;
s128 p, t;
init[first] += 1; p = t = init[first];
for(i=1; i cand[next[first]]) {
// re-sort
s32 mover, i;
// take it out of the list
mover = first;
first = next[first];
// Find the new spot
for(i=first;
(next[i] >= 0) && (cand[next[i]] < cand[mover]);
i=next[i]) { }
if ((i == first) && (cand[mover] < cand[i])) {
// insert back onto beginning
next[mover] = first;
first = mover;
} else if (i < 0) {
// stick on end
next[mover] = -1;
next[last] = mover;
last = mover;
} else {
// insert in middle
next[mover] = next[i];
next[i] = mover;
}
}
// Now check if first item in list is bigger than nextfact, if so we can
// insert a new item
if (cand[first] >= nextfact) {
s32 i;
// Add another element to the list
cand[free] = nextfact;
init[free] = 2;
len[free] = nf_len;
// insert to beginning
next[free] = first;
first = free;
free++;
// calculate the next nextfact
nf_root += 1;
nextfact *= nf_root;
nf_len++;
}
if (++tc >= 10000000) {
s128_str(cand[first], ss);
printf(" (up to %s...)\r", ss); fflush(stdout);
tc = 0;
}
}
printf("...\n");
printf("used %d nodes; elapsed time: %d \n",
free, ((int) (time(0) - st)));
pr5040_print_list(cand, init, len, next, first);
}