Problems & Puzzles: Puzzles

Puzzle 1028. Prime Generating Modular functions

Dmitry Kamenetsky sent the following nice puzzle

I found that

(671n mod2454)+(304n mod32)+(4373n mod199)

generates 38 distinct primes for n=1 to 38: 881,1531,2213,409,1091,1741,2423,619,1301,1951,179,829,1511,2161,389,1039,1721,2371,599,

Q1. Is this anything unusual and is there a good explanation for it?
Q2. Is there a function of the same form that generates more distinct primes?

Note: The function must be of the form ∑i(Ai*n mod Bi), where all Ai,Bi are positive integers.


During the week 16-22 January, 2021, contributions came from Dmitry Kameneteski, Adam Stinchcombe


Dmitry wrote:

I found a function that improves the answer to 41 primes:


Adam wrote:

You can turn any "primes in a.p." into a solution to this puzzle, so the Green-Tao theorem says there are arbitrarily long solutions to this puzzle.  For 1<n<m/a, (a*n) mod m = a*n and  (a*n) mod m + (m-a)*n mod m simplifies to m because (m-a)*n = m*n - a*n = m*(n-1) + (m-a*n) is congruent to m-a*n for small n.  Using the second concept you can march an a.p. "backwards" with a single summand.  For instance, the a.p. 199+210*n which is prime for n =0 to 9, can be written as 2089*n mod 2299, n=1 to 10.

The p.a.p. record, at 27, has large coefficients so Kamenetsky's example with small numbers is better (and longer):

224584605939537911 + 8129213923#n, for n=0 to 26, 2019, by Rob Gahan, PrimeGrid


Records   |  Conjectures  |  Problems  |  Puzzles