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,
1249,1931,127,809,1459,2141,337,1019,1669,2351,547,1229,1879,107,757,1439,2089,317,967.

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:
(n*639)mod558+(n*355)mod344+(n*1124)mod1066+(n*1294)mod1230+(n*175)mod179

***

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 + 81292139·23#·n, for n=0 to 26, 2019, by Rob Gahan, PrimeGrid

***

Records   |  Conjectures  |  Problems  |  Puzzles