Problems & Puzzles:
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:
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
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
I found a function that improves the answer to 41 primes:
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.
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