Problems & Puzzles: Puzzles

 Puzzle 855. Second follow up to Puzzle 853 Dmitry Kamenetsky sent the following follow up to Puzzle 853: x^12+488669 is composite for 616980 consecutive terms, namely for 0<=x<=616979 (see https://oeis.org/A122131). Can you find a polynomial f(x) that is composite for more terms before a prime appears? In other words, find f(x) that is composite for 1<=x<=K (where K>616980) and f(K+1) is prime. f(x) must be of the form A0+A1.x+A2.x^2+ ... + An.x^n, where A0 ... An are all integers Q. Send your best f(x) for this puzzle.

Emmanuel Vantieghem, Jan van Delden, Shyam Sunder Gupta,Seiji Tomita, Dmitry Kamenetsky and J. K. Andersen

***

Emmanuel wrote:

Here is a somewhat simpler polynomial :
f ( x ) = x^24 + 835379
It is prime for  x = 0  and  1961860  and composite in-between

...

Looking at the cited sequence  A122131  revealed that the function
x^12 + 488669  is prime at  1758120  and at  2467920  and composite for
709799  values in-between.
Thus, the function  (x + 1758120)^12 + 488669  is prime at  0  and  709800
and composite at all  x  between these values.
However, the coefficients are rather big ...

(Here is the polynomial form of that function :
872131901649211830923500570850684704430378886001984020525613056000000488669 + 5952712454093316708234936665420003442975761968479858170265600000000000 x +
18622118227147886319075007200765601287947745789046947840000000000 x^2 +
35306877473566245609088130504488888297248852541440000000000 x^3 +
45184898821197672866725987779616862710628352000000000 x^4 +
41121105563850178933611801496704991887360000000 x^5 +
27287456577381071119081993879535616000000 x^6 +
13303556352750700156538312294400000 x^7 +
4729326053096027346163200000 x^8 +
1195551322017212160000 x^9 +
204005071670400 x^10 +
21097440 x^11 +
x^12)

But, I think it will be worthwhile to look further for polynomials with smaller coefficients.

...

A more modest solution, still of degree  12  is
f ( x ) = x^12 + 3480749
It is prime for  x = 0  and  925470  and composite in-between.

...

Here are my best results for puzzle 855:
The polynomial :

f ( x ) = x^12 + 3480749
is prime for  x = 0  and  925470  and composite in-between.

If you allow bigger degree : the polynomial
f ( x ) = x^24 + 835379
It is prime for  x = 0  and  1961860  and composite in-between.

***

Jan wrote:

The given example x^12+488669 looks intimidating. But the underlying idea is simple.

Given a polynom of the form f[M,N](x)=x^M+N.

If (x,p)=1 we know that x^(p-1)=1 mod p. (p prime).

If we make sure that p-1|M and choose N=1 mod p we have f[M,N](x)=0 mod p for these x.

The idea is to choose an M with as much possible divisors d[i] of the form p[i]-1.

Then we search for N (as small as possible) such that N=-1 mod p[i] for these p[i].

If we denote the product of these p[i] by P then the smallest solution N is equal to P-1 and the others can be found by adding a multiple of P.

The only values  x where we could have f[M,N](x) prime are multiples of P, since we can’t exclude a different divisor q.

If we try M=12, or x^12+N, our set of primes is {2,3,5,7,13} having product P=2730, so we try N=2729+k*2730.

We merely test whether f[6,N](x) is prime, with x=m*2730 and try to find as large a value for m as possible.

 k N m # composites m/(k+1) 1 5459 11 30030 5,50 2 8189 66 180180 22,00 6 19109 68 185640 9,71 19 54599 104 283920 5,20 90 248429 153 417690 1,68 178 488669 226 616980 1,26 824 2252249 240 655200 0,29 900 2459729 282 769860 0,31 2811 7676759 523 1427790 0,19 9545 26060579 533 1455090 0,06

In blue the giving example. The number of composites can be improved by enlarging N, as shown. However if one measures the efficiency of N by computing m/(k+1), the solution x^6+8189 is the best (given in green).

The next M to try would probably be 36. The set of primes is {2,3,5,7,13,19,37}, P=1919190. We only miss a matching prime for the divisors 4 and 9. [If M=12 we miss 1 divisor on a total of 6].

 k N m # composites m/(k+1) 0 1919189 80 153535200 80,00 1 3838379 103 197676570 51,50 3 7676759 369 708181110 92,25 10 21111089 909 1744543710 82,64 156 301312829 1054 2022826260 6,71 720 1383735989 1062 2038179780 1,47 1123 2157169559 1924 3692521560 1,71

So x^36+7676759 is composite for x in [0,708181109].

Getting more composites is easy, just enlarge P (and thus M).

If one wants to find the “best” combination of (M,N) one should include M in a formula to measure efficiency.

Would something like m/(M*(k+1)) do?

***

Shyam wrote:

The polynomial x^12 + 7676759 is composite for 1427790 consecutive terms, namely for 0<=x<=1427789
However the polynomial (x+81590145)^12 + 2414684 is composite for 3426149 consecutive terms, namely for 1<=x<=3426149

Seiji wrote:

N: number of consecutive positive integer
f(x): composite for 1<=x<=N
f(N+1): prime number
N>700000

[f, N]
[x^12+2459729, 769859]
[x^12+3480749, 925469]
[x^12+2414684, 975974]

[x^24+337154, 702974]
[x^24+202019, 712529]
[x^24+111929, 723449]
[x^24+790334, 724814]
[x^24+346709, 739829]
[x^24+417689, 783509]
[x^24+54599,  835379]
[x^24+428154, 844024]
[x^24+148784, 918644]

Dmitry wrote:

Here are my results. zhekas (from the Russian forum) found a way to generate an arbitrary number of composite values for polynomial orders n>1. Take some order n. Find all primes p such that n divides by (p-1). Let P be the product of such primes, then the polynomial

f(x)=x^n + P - 1 will be composite for 0<=x<=P-1. But it may be composite for more values, so you need to check. In fact, f(x) will be prime only for values x=P*m-1, for some integer m>0. Now we can iterate over multipliers k that maximise the number of composites produced by f(x)=x^n+P*k - 1. The best results I got using this method are

f(x)=x^36+1919190*1124-1, which generates 1919190*1924=3692521560 composites.
f(x)=x^60+56786730*2090-1, which generates 56786730*3181=180638588130 composites.

If we are limited to small additive constants (less than 10 million) then the best results I got:

f(x)=x^60 + 1352064, which gives 1753628304 composites.
f(x)=x^120 + 293600, which gives 2012047652 composites.

For orders n, I found it useful to look at highly composite values:
P.S. The Russian forum is here: http://dxdy.ru/topic112848.html

***

J. K. wrote:

For any natural K, f(x) = (x-K-2)*(x-K-3) is composite for 1<=x<=K,
and f(K+1) = 2 is prime. Irreducible polynomials are more interesting.

x^180+7225713885389 is first prime for x = 4631682600534990, proved by Primo.
x^540+115471236091149548609 is first prp for x = 1489578945575829177069000.
x^1260+4554106624556364764691012209 for x = 22970913814262303873101465587240.