GENERATING THE LAZY CATERER'S SEQUENCE IN PYTHON LANGUAGE
AMRUHA AHMED
15th October,2023.
The lazy caterer's sequence provides you with a lucid way to calculate the maximum number of pieces of a disk shaped object which can be made using straight cuts.
The formula to generate this sequence is:
(n^2+n+2)/2 or simply nC0+nC1+nC2(if n>=2)
Where n represents the number of cuts made to the disk-like object.
In this blog post, I will be discussing about the generation of the lazy caterer's sequence using the formulae mentioned above.
METHOD-1
In this method, the formula of nC0+nC1+nC2 will be used to calculate the terms of the lazy caterer's sequence. The following things need to be kept in mind while following this approach:
- 1.When n=0, then the term of the sequence should not contain the values of nC1 and nC2 since 0C1 and 0C2 do not exist
- 2.When n=1, then the term of the sequence should not contain the value of nC2 since 1C2 does not exist.
VARIABLES REQUIRED:
- a-parameter to the fact()
- n-maximum number of cuts to be made
- term1-stores nC0
- term2-stores nC1
- term3-stores nC2
- i-loop counter
- finalterm-sum of term1,term2 and term3(substitution of formula)
FUNCTIONS REQUIRED:
- 1.main()-contains the steps required to calculate and display the numbers of sequence
- 2.fact()-recursive function to calculate the factorial of the parameter 'a'
ALGORITHM FOR THE MAIN FUNCTION:
- 1.Start
- 2. Accept the number of terms of the sequence to be generated in 'n'
- 3.Initialize term1, term2 and term3 to 0
- 4.Loop counter i is initialized to 0
- 5.While i is less than or equal to 'n' the following steps need to be repeated:
- (i)initialize finalterm to 0
- (ii)calculate term1(nC0) as fact(i)/fact(i-1)
- (iii) when i is not equal to 0 , execute the next statements otherwise make term2=0
- (iv) calculate term2(nC1) as fact(i)/(fact(i-1)*fact(1))
- (v)if i is not equal to 1 then move to the next step otherwise make term3 to 0
- (vi)calculate term3(nC2) as fact(i)/(fact(i-2)*fact(2))
- (vii)calculate finalterm as term1+term2+term3
- (viii)display finalterm
- 6.Stop
PROGRAM:
def fact(a): #function to calculate factorial
if a==0:
return 1
else:
return(a*fact(a-1))
n=int(input("Enter the maximum number of cuts to be made:"))
term1=0 #term1 =nC0
term2=0 #term2 for nC1
term3=0 #term3 for nC2
for i in range(0,n+1): #i is the loop counter
finalterm=0 #to store the sum of term1,term2 and term3(substitution of formula)
term1=int(fact(i)/(fact(i)*fact(0)))
if i!=0:
term2=int(fact(i)/(fact(i-1)*fact(1)))
if(i!=1):
term3=int(fact(i)/(fact(i-2)*fact(2)))
else:
term3=0
else:
term2=0
finalterm=term1+term2+term3
print("{}\t".format(finalterm),end="")
DRY RUN:
if n=4 then the following steps are executed in the loop:
OUTPUT:
Enter the maximum number of cuts to be made : 4
The lazy caterer's sequence is...
1 2 4 7 11
METHOD-2:
In this method, the formula of (n^2+n+2)/2 will be used to calculate the terms of the lazy caterer's sequence.
VARIABLES REQUIRED:
- i- loop counter
- n-number of terms of sequence to be generated (that is the maximum number of cuts that can be made to the object)
- temp-temporary variable
ALGORITHM FOR THE MAIN FUNCTION:
- 1.Start
- 2.Accept the number of terms of the sequence to be generated in 'n'
- 3.loop counter 'i' is initialized to 0
- 4. While the loop counter 'i' is less than or equal to n , the following steps need to be repeated:
- (i)declare temporary variable temp
- (ii) calculate (n^2+n+2)/2 and store in temp
- (iii)display value of temp
- (iv)increment i by 1
- 5.Stop
PROGRAM:
i=0 #loop counter
n=int(input("Enter the maximum number of cuts to be made:"))
print("The lazy caterer's Sequence is ...")
while i<=n:
temp=int(((i*i)+i+2)/2) #temporary variable
print("{}\t".format(temp),end="")
i=i+1
DRY RUN:
if n=4 then the following steps are executed in the loop:
OUTPUT:
Enter the maximum number of cuts to be made : 4
The lazy caterer's sequence is...
1 2 4 7 11