login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A269926 Number of partitions of n into rational parts a/b such that 1<=a,b<=n and gcd(a,b)=1. 0
1, 4, 33, 385, 11483, 305684 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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

LINKS

Table of n, a(n) for n=1..6.

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 }.

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

Cf. A018805, A209489.

Sequence in context: A293020 A293193 A295256 * A156132 A215364 A213641

Adjacent sequences:  A269923 A269924 A269925 * A269927 A269928 A269929

KEYWORD

nonn,more

AUTHOR

Robert C. Lyons, Mar 07 2016

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 19 06:37 EST 2020. Contains 331033 sequences. (Running on oeis4.)