Definition

---

Euclid(c, m)

Euclid(c, m) is the set resulting from the application of the eXtended Eratosthenes Sieve to the base sequence c + m k, with k ranging from 1 to infinity, and with c relatively prime to m and such that 0 < c < m.

For evident reasons, to calculate Euclid(c, m) we have to stop k at a top t value. So we can write the operating definition of Euclid(c, m) as follows:

Euclid(c, m) = Euclid[ c, m, t ] for t tending to infinity

Here is the formulation as a Mathematica function:

Euclid[ c, m, t ]

Euclid[ c_Integer, m_Integer, t_Integer ] :=
  pXES[ Range[ c + m, t, m ] ]  /; IsCoprime[ c, m ] && 0 < c < m && IsNaturalZ[ t ]

It gives the terms of Euclid(c, m) up to t.

Note that Euclid and other functions use p-rivate versions of the exposed functions to speed up computation time, reducing tests on arguments.

Example

• oddPrimes = Euclid[ 1, 2, 100 ]
  {3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}

• Euclid[ 1, 3, 100 ]
  {4, 7, 13, 19, 25, 31, 37, 43, 61, 67, 73, 79, 97}

  Euclid[ 2, 3, 100 ]
  {5, 8, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89}

• Euclid[ 9, 10, 100 ]
  {19, 29, 39, 49, 59, 79, 89}

Properties

---

As you can see in the example above, the terms of the Euclid(c, m) set are prime numbers only for Euclid(1, 2), but they are composite and prime in any other case. To study a little bit deeper the divisibility of the terms of the Euclid(c, m) set I provided the following functions:

CompositeTerms[ set ]

CompositeTerms[ set_List ] := Cases[ set, x_ /; Not[ PrimeQ[ x ] ] ] /; IsNaturalZ[ set ]

It gives the subset of the composite numbers in the set.

CompositeRatio[ set ]

CompositeRatio[ {} ] := 0.0
CompositeRatio[ set_List ] := N[ 100 Length[ CompositeTerms[ set ] ] / Length[ set ] ]

It gives the percentual of composite numbers in the set.

PlotCompositeRatio[ c, m, start, stop, step ]

PlotCompositeRatio[ c_Integer, m_Integer, start_Integer, stop_Integer, step_Integer ] :=
  ListPlot[ Table[ {k, CompositeRatio[ Euclid[ c, m, k ] ]}, {k, start, stop, step} ],
    PlotJoined -> True,
    PlotRange -> All,
    Axes -> False,
    Frame -> True,
    FrameTicks -> {Automatic, Range[ 1, 100, 2 ]},
    GridLines -> {Range[ start, stop, step ], Range[ 1, 100, 1 ]}
  ]

It plots CompositeRatio[ Euclid[ c, m, k ] ] with k ranging from start to stop, by step.

Example

• CompositeRatio[ Euclid[ 1, 2, 1000 ] ]
  0

• CompositeRatio[ Euclid[ 1, 3, 500 ] ]
  8.16327

  CompositeRatio[ Euclid[ 2, 3, 500 ] ]
  2.04082

  CompositeRatio[ Euclid[ 1, 3, 5000 ] ]
  2.94118

  CompositeRatio[ Euclid[ 2, 3, 5000 ] ]
  0.295858

  PlotCompositeRatio[ 1, 3, 0, 10000, 500 ]
  

  PlotCompositeRatio[ 2, 3, 0, 10000, 500 ]
  

• Ec1m17t1000 = Euclid[ 1, 17, 1000 ]
  {18, 35, 103, 137, 239, 307, 341, 409, 443, 613, 647, 817, 851, 919, 953}

  CompositeRatio[ Ec1m17t1000 ]
  33.3333

  Ec1m17t10000 = Euclid[ 1, 17, 10000 ]
  {18, 35, 103, 137, 239, 307, 341, 409, 443, 613, 647, 817, 851, 919, 953, 1021, 1123, 1157, 1259, 1327, 1361, 1429, 1531, 1667, 1769, 1871, 1973, 2143, 2347, 2381, 2551, 2687, 2789, 2857, 2993, 3061, 3163, 3299, 3469, 3571, 3673, 3877, 3911, 4013, 4217, 4421, 4489, 4523, 4591, 4897, 4931, 4999, 5101, 5237, 5407, 5441, 5849, 6053, 6121, 6257, 6359, 6427, 6529, 6563, 6733, 6869, 6971, 7039, 7243, 7379, 7481, 7549, 7583, 7753, 8059, 8093, 8161, 8263, 8297, 8467, 8501, 8807, 9011, 9181, 9283, 9419, 9487, 9521, 9623, 9929}

  CompositeRatio[ Ec1m17t10000 ]
  13.3333

  CompositeRatio[ Euclid[ 1, 17, 40000 ] ]
  7.82918

• CompositeRatio[ Euclid[ 10, 17, 10000 ] ]
  13.0435

  CompositeRatio[ Euclid[ 11, 17, 10000 ] ]
  13.0435

  CompositeRatio[ Euclid[ 10, 17, 40000 ] ]
  7.19178

  CompositeRatio[ Euclid[ 11, 17, 40000 ] ]
  6.66667

• PlotCompositeRatio[ 16, 17, 0, 100000, 5000 ]