---

Development of Algorithmic Constructions

22:13:16 19.Apr 2024

---

Polynom = x^2+1

1. Algorithm

a:=1;
b:=0;
c:=1;


liste_max:=100000;

sieving:=proc (stelle, p)
begin
   while (stelle<=liste_max) do
     erg:=liste[stelle];
     while(erg mod p=0) do
        // Divison of the stored f(x) by the prime
        erg:=erg /p;
     end_while;
     liste[stelle]:=erg;
     stelle:=stelle+p;
   end_while;
end_proc;

// Calculation of the values of the polynom for x from 0 to liste_max
for x from 0 to liste_max do
   p:=abs (a*x^2+b*x+c);
   while (p mod 2=0) p:=p/2;
   liste [x]:=p;
end_for;

for x from 0 to liste_max do
    p:=liste[x];

    if (p>1) then

      // Printing the Primes
      print (x, p);

      // 1. Sieving
      sieving (x+p,  p);

      t:=(-x-b/a) mod p;
      if t=0 then t:=p; end_if;

      // 2. Sieving
      sieving (t, p);

    end_if;

end_for;

 2. Mathematical background
Lemma: If p | f(x) then also p | f(x+p) and  p | f(-x-b/a)

a)  p | f(x)   <=> ax^2 + bx + c = 0                       mod p
    p | f(x+p) <=> a(x+p)^2 + b(x+p) + c = 0               mod p
               <=> ax^2 + 2axp + ap^2 + bx + bp + c = 0    mod p
               <=> ax^2 + bx + c = 0                       mod p

    Thus if p | f(x) then p | f(x+p)

b)  if b = 0 mod a
    p | f(x)       <=> ax^2 + bx + c = 0                         mod p
    p | f(-x-b/a)  <=> a(-x-b/a)^2 + b(-x-b/a) + c = 0           mod p
                   <=> ax^2 + 2bx + b^2/a - bx - b^2/a + c = 0   mod p
                   <=> ax^2 + bx + c = 0                         mod p

    Thus if p | f(x)  then p | f(-x-b/a)



 3. Correctness of the algorithm
The proof for this polynom is similar to the proof for the polynom f(x)=x^2-4x+1.

a) First terms for the polynom f(x) = x^2+1

f(0)=1
f(1)=1
f(2)=5
f(3)=1
f(4)=17
f(5)=13
f(6)=37
f(7)=1
f(8)=1
f(9)=41
f(10)=101
f(11)=61
f(12)=29
f(13)=1
f(14)=197
f(15)=113
f(16)=257
f(17)=1
f(18)=1
f(19)=181
f(20)=401
f(21)=1
f(22)=97
f(23)=53
f(24)=577
f(25)=313
f(26)=677
f(27)=73
f(28)=157
f(29)=421
f(30)=1
f(31)=1
f(32)=1
f(33)=109
f(34)=89
f(35)=613
f(36)=1297
f(37)=137
f(38)=1
f(39)=761
f(40)=1601
f(41)=1
f(42)=353
f(43)=1
f(44)=149
f(45)=1013
f(46)=1
f(47)=1
f(48)=461
f(49)=1201
f(50)=1
f(51)=1301
f(52)=541
f(53)=281
f(54)=2917
f(55)=1
f(56)=3137
f(57)=1
f(58)=673
f(59)=1741
f(60)=277
f(61)=1861
f(62)=769
f(63)=397
f(64)=241
f(65)=2113
f(66)=4357
f(67)=449
f(68)=1
f(69)=2381
f(70)=1
f(71)=2521
f(72)=1
f(73)=1
f(74)=5477
f(75)=1
f(76)=1
f(77)=593
f(78)=1217
f(79)=3121
f(80)=173
f(81)=193
f(82)=269
f(83)=1
f(84)=7057
f(85)=3613
f(86)=569
f(87)=757
f(88)=1549
f(89)=233
f(90)=8101
f(91)=1
f(92)=1693
f(93)=1
f(94)=8837
f(95)=4513
f(96)=709
f(97)=941
f(98)=1
f(99)=1

b) Substitution of the polynom
The polynom f(x)=x^2+1  could be written as f(y)= y^2+1 with x=y+0

c) Backsubstitution

Beside by backsubstitution you get an estimation for the huge of the primes with p | f(x) and p < f(x)

f'(y)>(2y-1) with with y=x+0
f'(x)>2x-1  with x > 1

4. Infinity of the sequence

The first prime values for the polynom fx)=x^2+1 are
f(0)=1
f(1)=2
f(2)=5
f(3)=1
f(4)=17

Supposing that the sequence f(5)-f(oo)=1

p1=2
p2=5
p3=17

are the first primes

choose a special x1, x2 and x3 for the primes

x1=2
x2=4
x3=5

(Other values are also possible, f(xi) should not be divisible by pi)

With the help of the chinese remainder theorem you could solve the
equitations :

x=0 mod 2  f(0)=1  not divisible by 2
x=4 mod 5  f(4)=17 not divisible by 5
x=5 mod 17 f(5)=26 not divisible by 17

The solution is x=124 mod 170

f(124) is not divisible by the primes 2, 5, 17
f(124)=15377 which is by chance a primes.

By this way you could calculate a special x taking the first primes of the sequence calculated by the algorithm 
and you get as result a special f(x) which is either a prime or consists of primes which are not yet in the sequence.

Therefore the sequence of the reducible primes at least for the primes which appear as divisor of f(x) is infinite.

5. Sequence of the polynom with 1

6. Sequence of the polynom (only primes)

7. Distribution of the primes

8. Check for existing Integer Sequences by OEIS

Found in Database : 1, 1, 5, 1, 17, 13, 37, 1, 1, 41, 101, 61, 29, 1, 197, 113, 257, 1, 1, 181,
Found in Database : 5, 17, 13, 37, 41, 101, 61, 29, 197, 113, 257, 181, 401, 97, 53, 577, 313, 677, 73, 157, 421, 109, 89, 613, 1297, 137, 761,
Found in Database : 5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97, 101, 109, 113, 137, 149,