Sequence A064224: Two Distinct Representations as Product of Consecutive Integers>1
This sequence, Sloane's A064224, 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:
19958400 = 3×4×5×6×7×8×9×10×11 = 5×6×7×8×9×10×11×12
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 immediately see that the equation is true without doing any more 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:
259459200 = 5×6×7×8×9×10×11×12×13 = 8×9×10×11×12×13×14×15
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:
210 → 259459200
720 → 5040
175560 → 36055954861352887137197787308347629783163600896000000000
17297280 → 6244042313569035223343873483125151604764341428027427022254596874567680000000000000
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". In the GCC compiler you can use "typedef __attribute__((__mode__(__TI__))) s128;" to get a 128-bit integer type. "s128_str" converts a 128-bit integer to a string. "s32" is a normal 32-bit signed integer type.
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; i<len; i++) { if (i>0) { 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<len[first]; i++) { t += 1; p *= t; } cand[first] = p; // len[] stays the same; next[] is about to be fixed } if (cand[first] > 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<len[first]; i++) { t += 1; p *= t; } cand[first] = p; // len[] stays the same; next[] is about to be fixed } if (cand[first] > 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); }Some other sequences are discussed here.
This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2014 Dec 07.
s.27