login
A269926
Number of partitions of n into rational parts a/b such that 1<=a,b<=n and gcd(a,b)=1.
0
1, 1, 4, 33, 385, 11483, 305684, 24306812, 1472403740, 247008653639, 34519470848749, 12828108172960015, 1928570926371392597
OFFSET
0,3
COMMENTS
A018805 is the number of rational parts a/b, such that 1<=a,b<=n and gcd(a,b)=1.
EXAMPLE
For n=2, the rational parts a/b, such that 1<=a,b<= n and gcd(a,b)=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 }.
MAPLE
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
MATHEMATICA
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 *)
PROG
(Sage)
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)
(Sage)# 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)
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Robert C. Lyons, Mar 07 2016
EXTENSIONS
a(0), a(7)-a(12) from Alois P. Heinz, Mar 14 2020
STATUS
approved