Problems & Puzzles:
Problems
Problem 27. Congruent K contiguous products of
consecutive numbers.
At 12/11/99 Landon Curt Noll wrote: "Here is a puzzle for
your pages… Erdös, in a letter dated 79-10-31 observed that
3*4 = 5*6*7 = 1 mod 11 and asked for the least prime p such that three
consecutive products of integers = 1 mod p. He suggests that such
primes p exist for any number of such congruent products.
His problem was first published in the 1st edition of "Unsolved
Problems in Number Theory", R. K. Guy, as problem A15.
Landon Noll and Chuck
Simmons solved Erdös' problem by solving a more general
problem of q1! = q2! = ... = qn! mod p, where q1 < q2 < ... <
qn. See http://reality.sgi.com/chongo/tech/math/n-sequence.html
(detected as borken 1/9/01)
By my side I have re-calculated the least p for K>2 product of
consecutive integers, going back to the original Erdös
question (that is to say, by-passing temporarily the Noll &
Simons generalization)
Here are the results, where K is - to be precise - the number of
contiguous products of consecutive integers:
K= 2 : P(3 , 4) = P(5 , 7)=1 mod 11 ………. Note: P(5,7) means 5x6x7 = 210
K= 3 : P(2 , 5) = P(6 , 11) = P(12 , 15) = 1 mod 17
K= 4 : P(2 , 4)=P(5 , 8)=P(9 , 11)=P(12 , 21)=1 mod 23
K= 5 & 6 : P(8 , 9) = P(10 , 19) = P(20 , 51) = P(52 , 61) = P(62 ,
63) = P(64 , 70) = 1 mod 71
K= 7 & 8 : P(29 , 50) = P(51 , 122) = P(123 , 183) = P(184 , 250) =
P(251 , 289) = P(290 , 500) = P(501 , 539) = P(540 , 555) = 1 mod 599
K= 9: P(2 , 611) = P(612 , 723) = P(724 , 749) = P(750 , 805) = P(806 ,
2205) = P(2206 , 2261) = P(2262 , 2287) = P(2288 , 2399) = P(2400 ,
3009) = 1 mod 3011
According to R. K. Guy, Makowski found results
corresponding to K = 3 & 4 and W. Narkiewicz the results
corresponding to K = 7, 8 & 9.
But neither in the original version of the Erdös question, nor in
the Noll & Simmons generalization, has been produced
an example for K=10 such products, weakening the Erdös
conjecture. Would you like to try to get
an example for K=>10 ? *
_____
* If you consider that the solution for K= 9 can be
viewed as an example for K=10 introducing P(1,1) as valid, then just
change your search to K=>11.

At last one contribution for
this old puzzle!
J. K. Andersen wrote (May 4,
2007):
The broken
http://reality.sgi.com/chongo/tech/math/n-sequence.html is now
at
http://isthe.com/chongo/tech/math/n-sequence.html
K= 10 : P(2452 , 2867) = P(2868 , 4768) = P(4769 , 10383) = P(10384 ,
18707) = P(18708 , 19589) = P(19590 , 19965) = P(19966 , 22981) =
P(22982 , 24673) = P(24674 , 26322) = P(26323 , 27263) = 1 mod 27901
K= 11 : P(2 , 3924) = P(3925 , 7291) = P(7292 , 7427) = P(7428 , 18519)
= P(18520 , 24931) = P(24932 , 26081) = P(26082 , 27231) = P(27232 ,
33643) = P(33644 , 44735) = P(44736 , 44871) = P(44872 , 52161) = 1 mod
52163
K= 12 : P(9081 , 137131) = P(137132 , 163149) = P(163150 , 240819) =
P(240820 , 382404) = P(382405 , 473719) = P(473720 , 476285) = P(476286
, 482827) = P(482828 , 486833) = P(486834 , 565418) = P(565419 , 592882)
= P(592883 , 624737) = P(624738 , 730034) = 1 mod 778699
K= 13 : P(653599 , 689779) = P(689780 , 789933) = P(789934 , 845577) =
P(845578 , 869139) = P(869140 , 946501) = P(946502 , 950026) = P(950027
, 1410794) = P(1410795 , 1428147) = P(1428148 , 1505509) = P(1505510 ,
1529071) = P(1529072 , 1584715) = P(1584716 , 1684869) = P(1684870 ,
2374648) = 1 mod 2374649
K= 14 : P(816489 , 1251081) = P(1251082 , 3384225) = P(3384226 ,
4112650) = P(4112651 , 4237275) = P(4237276 , 4431559) = P(4431560 ,
4467010) = P(4467011 , 4835062) = P(4835063 , 7328694) = P(7328695 ,
7385077) = P(7385078 , 7415726) = P(7415727 , 8460938) = P(8460939 ,
8689396) = P(8689397 , 9295594) = P(9295595 , 9661614) = 1 mod 10428007
I will submit the extension 27901, 52163, 778699, 2374649, 10428007 to
http://www.research.att.com/~njas/sequences/A060427
1) can you give us an idea of
the approach used by you in order to get
these large records? 2) Do you know what is the theoretical interest in
this question by Erdös?
No solution product can
contain a multiple of p, because the product would
become 0 (mod p).
A solution remains unchanged modulo p if a multiple of p is added to
each
number. For example, the given solution for K=2 is 3*4 = 5*6*7 = 1 (mod
11).
This has the equivalent solution 14*15 = 16*17*18 = 1 (mod 11).
We only have to consider integers below p to find all solutions.
For prime p and q1 < q2 < p, if q1! = q2! (mod p), then (q1+1)*...*q2 =
1
(mod p). My computation used rather brute force on this.
For each prime p, the value of q! (mod p) was computed for q = 2 to p-1.
This was done with modular multiplication modulo p, in order to keep all
numbers below p^2, so computations are fast.
A table was used to count the number of occurrences of each value of q!
(mod
p).
The listed solutions correspond to a record number of occurrences of a
value.
I don't know why Erdös was interested in this problem.
***
|