A115855 -id:A115855 - cp's OEIS frontend

A115856 First differences of A115855.

1, 2, 3, 6, 9, 14, 23, 48, 82, 55, 250, 100, 469, 2213, 2232, 296, 6623, 489, 29495, 89362, 35815, 1254, 259171, 411355, 176134, 952660, 3819125, 4564, 9371908, 6841, 13668113, 47144847, 6769988, 403602715, 672086464, 21636, 53588139, 1454972415, 6300092899, 44582

Offset: 1

Reinhard Zumkeller, Feb 01 2006

nonn

By definition of A115855, a(n+1) is the number of ways 1 can be written as sum of distinct positive fractions having no denominator larger than n, and at least one equal to n (in its reduced form). - M. F. Hasler, Jul 14 2016

Cf. A116085, A119983.

Table[Length@ Select[Flatten[Map[IntegerPartitions[1, {#}, Rest@ Union[Flatten@ TensorProduct[#, 1/#] &@ Range@ n /. {Integer -> 0, k /; k > 1 -> 0}]] &, Range@ n], 1], Total@ # == 1 && MemberQ[Union@ Denominator@ #, n] &], {n, 2, 25}] (* Michael De Vlieger, Jul 15 2016 *)

a(n) = A115855(n+1) - A115855(n).

a(A000040(n)-1) = A000041(A000040(n)) - 1.

a(20)-a(27) from Michael De Vlieger, Jul 15 2016

More terms from Jinyuan Wang, Dec 12 2024

A119983 Number of ways to partition 1 into reduced fractions i/j with j <= n.

Original entry on oeis.org

1, 2, 4, 7, 13, 22, 36, 59, 107, 189, 244, 494, 594, 1063, 3276, 5508, 5804, 12427, 12916, 42411, 131773, 167588, 168842, 428013, 839368, 1015502, 1968162, 5787287, 5791851, 15163759, 15170600, 28838713, 75983560, 82753548, 486356263, 1158442727, 1158464363

Offset: 1

Franklin T. Adams-Watters, Aug 01 2006

nonn

The reduced fractions are the Farey fractions of order n (A005728). - Robert G. Wilson v, Aug 30 2010

			a(3) = 4; 1 = 1/1 = 1/2 + 1/2 = 2/3 + 1/3 = 1/3 + 1/3 + 1/3.

Cf. A000041, A020473, A115855 (one less), A115856.

Cf. A154886, A154888. - Reinhard Zumkeller, Jan 17 2009

Farey[n_] := Union@ Flatten@ Table[a/b, {b, n}, {a, b}]; f[n_] := Length@ IntegerPartitions[1, All, Farey@ n]; Array[f, 27] (* Robert G. Wilson v, Aug 30 2010 *)

For p prime, a(p) = a(p-1) + P(p) - 1, where P is the partition function (A000041).

Definition corrected by Reinhard Zumkeller, Jan 17 2009
a(21)-a(27) from Robert G. Wilson v, Aug 30 2010
More terms from Jinyuan Wang, Dec 12 2024

A116084 Number of partitions of 1 into distinct fractions i/j with 1<=i

Original entry on oeis.org

0, 0, 1, 2, 4, 6, 10, 15, 23, 36, 47, 70, 87, 132, 283, 434, 471, 772, 825, 1834, 4368, 5545, 5648, 9923, 16464, 19943, 32323, 75912, 76167, 140801, 141140, 238513, 537696, 598295, 2556064, 4674084, 4674843, 4985385, 9716586, 23983711, 23984970, 48523605, 48525214

Offset: 1

Reinhard Zumkeller, Feb 04 2006

nonn

Partial sums of A116085, which is more elementary to compute, cf. examples. Sequence A154888 has an equivalent definition except that i=j is allowed there, which yields the one-term sum 1/1 as an additional possibility, and thus A154888(n) = a(n)+1. Sequence A115855 is also about the same problem but does not require the fractions to be distinct. - M. F. Hasler, Jul 14 2016

			a(4) = # [1/3+2/3, 1/4+3/4] = 2;
a(5) = a(4) + # [1/5+4/5, 2/5+3/5] = 2 + 2 = 4;
a(6) = a(5) + # [1/6+5/6, 1/6+1/3+1/2] = 4 + 2 = 6.

Cf. A000009, A038566, A038567, A115855, A116085.

Equals A154888(n) - 1.

Table[Length@ Select[Union /@ Flatten[Map[IntegerPartitions[1, {#}, Rest@ Union[Flatten@ TensorProduct[#, 1/#] &@ Range@ n /. {Integer -> 0, k /; k > 1 -> 0}]] &, Range@ n], 1], Total@# == 1 &], {n, 25}] (* Michael De Vlieger, Jul 14 2016, after Robert G. Wilson v at A154888 *)

A116085(n) = a(n+1) - a(n).

a(n) = Sum_{k=1..n-1} A116085(k), cf. examples. - M. F. Hasler, Jul 14 2016

a(24)-a(34) from Don Reble, Jul 13 2016
a(35)-a(41) from Giovanni Resta, Jul 15 2016
a(42)-a(43) from Jinyuan Wang, Dec 12 2024

A269926 Number of partitions of n into rational parts i/j such that 1 <= i,j <= n and gcd(i,j) = 1.

Original entry on oeis.org

1, 1, 4, 33, 385, 11483, 305684, 24306812, 1472403740, 247008653639, 34519470848749, 12828108172960015, 1928570926371392597, 1431184075250830915405, 670210514199929067110226, 1159071708111028412649897690, 702243565303276226975262410876, 1815785932270337215073101716635095

Offset: 0

Robert C. Lyons, Mar 07 2016

nonn

A018805 is the number of rational parts i/j, such that 1 <= i,j <= n and gcd(i,j) = 1.

			For n = 2, the rational parts i/j, such that 1 <= i,j <= n and gcd(i,j) = 1, are: { 1/1, 1/2, 2/1 }. a(2) = 4 because 2 can be partitioned into the following 4 partitions: { 1/2, 1/2, 1/2, 1/2 }, { 1/1, 1/2, 1/2 }, { 1/1, 1/1 }, { 2/1 }.

Cf. A018805, A115855, A119983.

a:= proc(n) option remember; local l, b; l, b:=
      sort([{seq(seq(x/y, y=1..n), x=1..n)}[]]),
      proc(r, i) option remember; `if`(r=0, 1,
        `if`(i<1, 0, add(b(r-l[i]*j, i-1), j=
        `if`(i=1, r/l[i], 0..r/l[i]))))
      end; b(n, nops(l))
    end:
seq(a(n), n=0..7);  # Alois P. Heinz, Mar 14 2020

a[n_] := a[n] = Module[{l, b}, l = Union@ Flatten@ Table[x/y, {y, 1, n}, {x, 1, n}]; b[r_, i_] := b[r, i] = If[r == 0, 1, If[i < 1, 0, Sum[b[r - l[[i]] j, i - 1], {j, If[i == 1, r/l[[i]], Range[0, r/l[[i]]]]}]]]; b[n, Length[l]]];
a /@ Range[0, 7] (* Jean-François Alcover, Nov 29 2020, after Alois P. Heinz *)

from itertools import combinations_with_replacement
seq = []
for n in range( 1, 5 ):
    rationals = set()
    for a in range( 1, n+1 ):
        for b in range( 1, n+1 ):
            rational = Rational( (a, b) )
            rationals.add( rational )
    partition_count = 0
    for r in range( 1, n^2 + 1 ):
        for partition in combinations_with_replacement( rationals, r ):
            if sum( partition ) == n:
                partition_count += 1
    seq.append( partition_count )
print(seq)

# Faster version
def count_combinations( n, values, r ):
    combo = [ None ] * r
    level = 0
    min_index = 0
    count = 0
    return get_count( n, values, r, combo, level, min_index, count )
def get_count( n, values, r, combo, level, min_index, count ):
    if level < r:
        for i in range( min_index, len( values ) ):
            combo[level] = values[i]
            if sum( combo[0:level] ) < n:
                count = get_count( n, values, r, combo, level+1, i, count )
    else:
        if sum( combo ) == n:
            count += 1
    return count
seq = []
for n in range( 1, 5 ):
    rational_set = set()
    for a in range( 1, n+1 ):
        for b in range( 1, n+1 ):
            rational = Rational( (a, b) )
            rational_set.add( rational )
    rationals = sorted( list( rational_set ) )
    partition_count = 0
    for r in range( 1, n^2 + 1 ):
        partition_count += count_combinations( n, rationals, r )
    seq.append( partition_count )
print(seq)

a(0), a(7)-a(12) from Alois P. Heinz, Mar 14 2020

More terms from Jinyuan Wang, Dec 12 2024

cp's OEIS Frontend

A115856 First differences of A115855.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

Extensions

A119983 Number of ways to partition 1 into reduced fractions i/j with j <= n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A116084 Number of partitions of 1 into distinct fractions i/j with 1<=i

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A269926 Number of partitions of n into rational parts i/j such that 1 <= i,j <= n and gcd(i,j) = 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Sage

Sage

Extensions