A075189 -id:A075189 - cp's OEIS frontend

A075188 Number of times that the numerator of a sum generated from the set 1, 1/2, 1/3,..., 1/n is prime.

0, 1, 3, 9, 19, 43, 79, 162, 307, 607, 1075, 2186, 3872, 7573, 15101, 29139, 52295, 104953, 189915, 379275, 754081, 1462115, 2675851, 5351541, 10254019, 19987942, 38901233, 77620568, 144021667, 288428481, 537642772, 1056802340, 2113152353, 4138261885

Offset: 1

T. D. Noe, Sep 08 2002

Note that for each n there are only 2^(n-1) new sums to consider. Surprisingly, nearly half of the sums have a prime numerator. For the number of distinct primes, see A075189. For the largest generated prime, see A075226. For the smallest odd prime not generated, see A075227.

A217712(n) = number of primes occurring exactly once as numerators. - Reinhard Zumkeller, Jun 02 2013

			a(3) = 3 because 3 sums yield prime numerators: 1+1/2 = 3/2, 1/2+1/3 = 5/6 and 1+1/2+1/3 = 11/6.

Cf. A001008, A075135, A075189, A075226, A075227.

Cf. A010051.

import Data.Ratio (numerator)
a075188 n = a075188_list !! (n-1)
a075188_list = f 1 [] where
   f x hs = (length $ filter ((== 1) . a010051') (map numerator hs')) :
            f (x + 1) hs' where hs' = hs ++ map (+ recip x) (0 : hs)
-- Reinhard Zumkeller, May 28 2013

Needs["DiscreteMath`Combinatorica`"]; maxN=20; For[cnt=0; lst={}; 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], cnt++ ]]; AppendTo[lst, cnt]]; lst

a(21)-a(25) by Reinhard Zumkeller, May 28 2013
a(26)-a(31) from Chai Wah Wu, Feb 14 2022
a(32)-a(34) from Sean A. Irvine, Feb 10 2025

A075226 Largest prime in the numerator of the 2^n sums generated from the set 1, 1/2, 1/3,..., 1/n.

Original entry on oeis.org

3, 11, 19, 137, 137, 1019, 2143, 7129, 7129, 78167, 81401, 1085933, 1111673, 1165727, 2364487, 41325407, 41325407, 796326437, 809074601, 812400209, 822981689, 19174119571, 19652175721, 99554817251, 100483070801

Offset: 2

T. D. Noe, Sep 08 2002

For the smallest odd prime not generated, see A075227. For information about how often the numerator of these sums is prime, see A075188 and A075189. The Mathematica program also prints the subset that yields the largest prime. For n <=20, the largest prime occurs in a sum of n-2, n-1, or n reciprocals.

			a(3) =11 because 11 is largest prime numerator in the three sums that yield primes: 1+1/2 = 3/2, 1/2+1/3 = 5/6 and 1+1/2+1/3 = 11/6.

Chai Wah Wu, Table of n, a(n) for n = 2..441 (terms 2..100 from Martin Fuller)
Martin Fuller, PARI program

Cf. A001008, A075135, A075188, A075189, A075227, A010051, A217712.

import Data.Ratio (numerator)
a075226 n = a075226_list !! (n-1)
a075226_list = f 2 [recip 1] where
   f x hs = (maximum $ filter ((== 1) . a010051') (map numerator hs')) :
            f (x + 1) hs' where hs' = hs ++ map (+ recip x) hs
-- Reinhard Zumkeller, May 28 2013

Needs["DiscreteMath`Combinatorica`"]; maxN=20; For[t={}; lst={}; mx=0; i=0; n=2, n<=maxN, n++, While[i<2^n-1, i++; s=NthSubset[i, Range[n]]; k=Numerator[Plus@@(1/s)]; If[PrimeQ[k], If[k>mx, t=s]; mx=Max[mx, k]]]; Print[n, " ", t]; AppendTo[lst, mx]]; lst
Table[Max[Select[Numerator[Total/@Subsets[1/Range[n],{2,2^n}]],PrimeQ]],{n,2,30}] (* The program will take a long time to run. *) (* Harvey P. Dale, Jan 08 2019 *)

PARI
```
See Fuller link.
```

from math import gcd, lcm
from itertools import combinations
from sympy import isprime
def A075226(n):
    m = lcm(*range(1,n+1))
    c, mlist = 0, tuple(m//i for i in range(1,n+1))
    for l in range(n,-1,-1):
        if sum(mlist[:l]) < c:
            break
        for p in combinations(mlist,l):
            s = sum(p)
            s //= gcd(s,m)
            if s > c and isprime(s):
                c = s
    return c # Chai Wah Wu, Feb 14 2022

More terms from Martin Fuller, Jan 19 2008

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.

Original entry on oeis.org

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

T. D. Noe, Sep 08 2002

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

			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.

Cf. A001008, A075135, A075188, A075189, A075226.
Cf. A010051, A065091.
Cf. A217712.

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

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 *)

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

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

A217712 Number of primes occurring exactly once as numerators in sums generated from the set 1, 1/2, 1/3,..., 1/n.

Original entry on oeis.org

0, 1, 3, 3, 11, 13, 27, 54, 106, 168, 378, 142, 733, 1597, 1283, 3418, 8204, 10112, 24644, 7829, 32866, 78136, 178741, 37002, 256392, 650596, 1402914, 286854, 2053463

Offset: 1

Reinhard Zumkeller, Jun 02 2013

nonn

For information about how often the numerator of the generated sums is prime, see A075188 and A075189; for the largest generated prime, see A075226; for the smallest odd prime not generated, see A075227.

			For n=3 there are the following fractions as sums of 1, 1/2 and 1/3:
{1/3, 1/2, 5/6, 1, 4/3, 3/2, 11/6}, three numerators are prime and they occur exactly once, therefore a(3) = A075188(3) = A075189(3) = #{3, 5, 11} = 3;
n=4: adding 1/4 to the previous fractions gives together: 1/4, 1/3, 1/2, 1/3+1/4=7/12, 1/2+1/4=3/4, 5/6, 1, 5/6+1/4=13/12, 1+1/4=5/4, 4/3, 3/2, 4/3+1/4=19/12, 3/2+1/4=7/4, 11/6 and 11/6+1/4=25/12:
A075188(4) = #{7/12, 3/4, 5/6, 13/12, 5/4, 3/2, 19/12, 7/4, 11/6} = 9,
A075189(4) = #{3, 5, 7, 11, 13, 19} = 6,
a(4) = #{11, 13, 19} = 3.

Cf. A010051.

import Data.Ratio ((%), numerator)
import Data.Set (Set, empty, fromList, toList, union, size)
import Data.Set (member, delete, insert)
a217712 n = a217712_list !! (n-1)
a217712_list = f 1 empty empty where
   f x s s1 = size s1' : f (x + 1) (s `union` fromList hs) s1' where
     s1' = g s1 $ filter ((== 1) . a010051') $ map numerator hs
     g v []                    = v
     g v (w:ws) | w `member` v = g (delete w v) ws
                | otherwise    = g (insert w v) ws
     hs = map (+ 1 % x) $ 0 : toList s

A256221 Number of distinct nonzero Fibonacci numbers in the numerator of the 2^n sums generated from the set 1, 1/2, 1/3, ..., 1/n.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 8, 8, 8, 12, 12, 13, 13, 13, 13, 15, 15, 15, 17, 17, 17, 19, 21, 21, 23, 24, 25, 25, 25, 25, 25, 27

Offset: 1

Michel Lagneau, Mar 19 2015

For the largest generated Fibonacci number, see A256222. For the smallest Fibonacci number not generated, see A256223.

			a(4) = 4 because 4 sums yield distinct Fibonacci numerators: 1, 1 + 1/2 = 3/2, 1/2 + 1/3 = 5/6 and 1/2 + 1/3 + 1/4 = 13/12.

Cf. A000045, A075189, A010056, A256220, A256222, A256223.

S:= {0,1}: N:= {1}:
nfibs:= 10:
fibs:= {seq(combinat:-fibonacci(n),n=1..nfibs)}:
A[1]:= 1:
fibnums:= {1}:
for n from 2 to 24 do
    Sp:= map(`+`,S,1/n);
    N:= N union map(numer, Sp);
  Nmax:= max(N);
  S:= S union Sp;
  while combinat:-fibonacci(nfibs) < Nmax do nfibs:= nfibs+1; fibs:= fibs union {combinat:-fibonacci(nfibs)} od;
  newfibnums:= N intersect fibs;
  fibnums:= newfibnums;
  A[n]:= nops(fibnums);
od:
seq(A[n],n=1..24); # Robert Israel, Dec 09 2016

<<"DiscreteMath`Combinatorica`";maxN=23; For[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[IntegerQ[Sqrt[5*k^2+4]]||IntegerQ[Sqrt[5*k^2-4]],prms=Union[prms, {k}]]]; Print[Length[prms]]]

from math import gcd, lcm
from itertools import combinations
def A256221(n):
    m = lcm(*range(1,n+1))
    fset, fibset, mlist = set(), set(), tuple(m//i for i in range(1,n+1))
    a, b, k = 0, 1, sum(mlist)
    while b <= k:
        fibset.add(b)
        a, b = b, a+b
    for l in range(1,n//2+1):
        for p in combinations(mlist,l):
            s = sum(p)
            if (t := s//gcd(s,m)) in fibset:
                fset.add(t)
            if 2*l != n and (t := (k-s)//gcd(k-s,m)) in fibset:
                fset.add(t)
    if (t:= k//gcd(k,m)) in fibset: fset.add(t)
    return len(fset) # Chai Wah Wu, Feb 15 2022

Corrected and more terms added by Robert Israel, Dec 09 2016
a(29)-a(31) from Chai Wah Wu, Feb 15 2022
a(32) from Chai Wah Wu, Feb 16 2022

cp's OEIS Frontend

A075188 Number of times that the numerator of a sum generated from the set 1, 1/2, 1/3,..., 1/n is prime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Haskell

Mathematica

Extensions

A075226 Largest prime in the numerator of the 2^n sums generated from the set 1, 1/2, 1/3,..., 1/n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Extensions

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.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Haskell

Mathematica

Python

Extensions

A217712 Number of primes occurring exactly once as numerators in sums generated from the set 1, 1/2, 1/3,..., 1/n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Haskell

A256221 Number of distinct nonzero Fibonacci numbers in the numerator of the 2^n sums generated from the set 1, 1/2, 1/3, ..., 1/n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Python

Extensions