A075227 Smallest odd prime not occurring in the numerator of any of the 2^n subset sums generated from the set 1/1, 1/2, 1/3, ..., 1/n.

3, 5, 7, 17, 37, 43, 43, 151, 151, 409, 491, 491, 491, 1087, 2011, 3709, 3709, 7417, 7417, 7417, 19699, 30139, 35573, 35573, 40237, 40237, 132151, 132151, 158551, 158551, 245639, 245639, 961459, 1674769, 1674769, 1674769, 1674769, 4339207

Offset: 1

Author

T. D. Noe, Sep 08 2002

Keywords

• nonn
• nice
• more

Comments

The largest prime generated is given in A075226. For information about how often the numerator of these sums is prime, see A075188 and A075189.

Examples

			a(3) = 7 because 7 is the smallest prime not occurring in the numerator of any of the sums 1/1 + 1/2 = 3/2, 1/1 + 1/3 = 4/3, 1/2 + 1/3 = 5/6 and 1/1 + 1/2 + 1/3 = 11/6.
		

Crossrefs

Cf. A001008, A075135, A075188, A075189, A075226.

Cf. A010051, A065091.

Cf. A217712.

Programs

Haskell

import Data.Ratio ((%), numerator)
import Data.Set (Set, empty, fromList, toList, union)
a075227 n = a075227_list !! (n-1)
a075227_list = f 1 empty a065091_list where
   f x s ps = head qs : f (x + 1) (s `union` fromList hs) qs where
     qs = foldl (flip del)
          ps $ filter ((== 1) . a010051') $ map numerator hs
     hs = map (+ 1 % x) $ 0 : toList s
   del u vs'@(v:vs) = case compare u v
                      of LT -> vs'; EQ -> vs; GT -> v : del u vs
-- Reinhard Zumkeller, May 28 2013

Mathematica

Needs["DiscreteMath`Combinatorica`"]; maxN=20; For[lst={}; prms={}; i=0; n=1, n<=maxN, n++, While[i<2^n-1, i++; s=NthSubset[i, Range[n]]; k=Numerator[Plus@@(1/s)]; If[PrimeQ[k], AppendTo[prms, k]]]; prms=Union[prms]; j=2; While[MemberQ[prms, Prime[j]], j++ ]; AppendTo[lst, Prime[j]]]; lst
(* Second program; does not need Combinatorica *)
a[1] = 3; a[2] = 5; a[n_] := For[nums = (Total /@ Subsets[1/Range[n]]) // Numerator // Union // Select[#, PrimeQ]&; p = 3, p <= Last[nums], p = NextPrime[p], If[FreeQ[nums, p], Print[n, " ", p]; Return[p]]];
Table[a[n], {n, 1, 23}] (* Jean-François Alcover, Sep 10 2017 *)

Python

from sympy import sieve
from fractions import Fraction
fracs, newnums, primeset = {0}, {0}, set(sieve.primerange(3, 10**6+1))
for n in range(1, 24):
  newfracs = set(Fraction(1, n) + f for f in fracs)
  fracs |= newfracs
  primeset -= set(f.numerator for f in newfracs)
  print(min(primeset), end=", ") # Michael S. Branicky, May 09 2021

Extensions

a(21)-a(28) from Reinhard Zumkeller, May 28 2013

a(29)-a(33) from Jon E. Schoenfield, May 09 2021

a(34)-a(36) from Michael S. Branicky, May 10 2021

a(37)-a(38) from Michael S. Branicky, May 12 2021