user
Description

A positive integer **k** is said to be an Erdős–Woods number if it has the following property: there exists a positive integer **a** such that in the sequence (a, a + 1, …, a + k) of consecutive integers, each of the elements has a non-trivial common factor with one of the endpoints. In other words, **k** is an Erdős–Woods number if there exists a positive integer **a** such that for each integer **i** between 0 and k, at least one of the greatest common divisors gcd(a, a + i) or gcd(a + i, a + k) is greater than 1.

It can be shown that there are infinitely many such numbers. Moreover, if **k** is an E-W number for some integer **a**, then one can find an infinite number of other **a'**s using the formula **a(jq + 1)** where:

* **q** is the product of all odd prime factors of **a + k**; and
* **j** is any positive integer.

Example

16 is an E-W number (and also the first) for which the smallest value of **a** is 2184. This is because in the sequence 2184 to 2200 inclusive, the prime factors of the endpoints are:

* 2³ x 3 x 7 x 13 = 2184
* 2³ x 5² x 11 = 2200

and, if you check all the numbers between them, you will find that they all have a prime factor in common with at least one of the endpoints (2189 is divisible by 11, 2191 by 7, 2197 by 13 and the rest by either 2, 3, or 5).

Task

Compute and show here the first **20** E-W numbers together with their corresponding smallest value of **a**. If your language doesn't support arbitrary precision arithmetic, just compute and show as many as you can.

Extra credit

Do the same for the **next 20** E-W numbers.

Note

Although all the E-W numbers relevant to this task are even, odd examples do exist the first one being **k** = 903.

References

* OEIS sequence A059756: Erdős–Woods numbers.
* OEIS sequence A059757: Smallest values of a for a given E-W number k.
* Planet Math: Erdős–Woods numbers.
assistant
**Translation of**: Wren

**Translation of**: Julia

```
# 20220308 Raku programming solution

sub ew (\n) {

   my @primes = (^n).grep: *.is-prime;  

   # rosettacode.org/wiki/Horner%27s_rule_for_polynomial_evaluation#Raku
   my @divs = (^n).map: -> \p { ([o] map { p%%$_.Int + 2 * * }, @primes)(0) }

   my @partitions = [ 0, 0, 2**@primes.elems - 1 ] , ;

   sub ort(\x) { (@divs[x] +| @divs[n -x]).base(2).flip.index(1) } 

   for ((n^...1).sort: *.&ort).reverse {
      my \newPartitions = @ = (); 
      my (\factors,\otherFactors) = @divs[$_, n-$_];

      for @partitions -> \p {
         my (\setA, \setB, \rPrimes) = p[0..2];

         if (factors +& setA) or (otherFactors +& setB) {
            newPartitions.push: p and next 
         } 
         for (factors +& rPrimes).base(2).flip.comb.kv -> \k,\v {
            if (v == 1) {
               my \w = 1 +< k;   
               newPartitions.push: [ setA +^ w, setB, rPrimes +^ w ]
            }
         }
         for (otherFactors +& rPrimes).base(2).flip.comb.kv -> \k,\v {
            if (v == 1) {
               my \w = 1 +< k; 
               newPartitions.push: [ setA, setB +^ w, rPrimes +^ w ]
            }
         }
      }
      @partitions = newPartitions
   }

   my \result = $ = -1;
   for @partitions -> \p {
      my ($px,$py,$x,$y) = p[0],p[1],1,1;
      for @primes -> $p {
         $px % 2 and $x *= $p;
         $py % 2 and $y *= $p;
         ($px,$py) >>div=>> 2
      }
      my \newresult = ((n * expmod($x, -1, $y)) % $y) * $x - n;
      result = result == -1 ?? newresult !! min(result, newresult)
   }
   return result 
}

say "The first 20 Erdős–Woods numbers and their minimum interval start values are:";
for (16..116) { if (my $ew = ew $_) > 0 { printf "%3d -> %d\n",$_,$ew } } ;

```

Output:

Same as Wren example.