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.
 

***

 

 


Records   |  Conjectures  |  Problems  |  Puzzles