<jupyter_start><jupyter_text>I have created two very short functions. The first - frogJump - jumps the requisite number of lily pads (n)If it falls short it calls itself with the new target which is the previous target minus the pad reached. Otherwise it returns the number of attempts it took (i). Note that i must be set to 0 in the first call and is incremented by one in each subsequent call until the target is reached.Note that n is the number of the last lilypad, assuming the frog starts on pad 0The second function - simulateFrog - uses frogJump to calculate the average number of jumps to reach the target n. The average is calculated over s simulations<jupyter_code>def frogJump(n,i):
    r=randint(1,n)
    i+=1
    if r==n:
        return i
    else:
        return frogJump(n-r,i)

#This function returns the average number of jumps to reach target n in s attempts
def simulateFrog(n,s):
    a=0
    for i in range(s):
        a=a+frogJump(n,0)
    return a/s<jupyter_output><empty_output><jupyter_text>The following code creates a list of results for average jumps to lily pads from 1 to rIn each case we are averaging over s simulations<jupyter_code>r=10
s=1000000
tbFrog = [[0,0]]*r
for pads in range(1,r):   
    tbFrog[pads]=[pads,simulateFrog(pads,s)]
tbFrog<jupyter_output><empty_output><jupyter_text>It looks like this is the sum to n of the harmonic seriesThe harmonic series is 1 + 1/2 + 1/3 + 1/4 .... 1/nWe can check this for, say, n=9 (see below) and the result compares favourably with our first simulation<jupyter_code>n=9
s=0
for i in range(n):
    s=s+1/(i+1)
print (s)<jupyter_output>2.8289682539682537<jupyter_text>Now we perform the same for 1 million pads.  Below, the sum of the harmonic series is compared with the simulateFrog function (which is quick).  Finally a formula for the sum of the harmonic series is used to find another answer for the sum to 1/1million.  As you can see they are comparable.<jupyter_code>n=1000000
s=0
for i in range(n):
    s=s+1/(i+1)
print (s)
simulateFrog(1000000,1000000)
#There is no simple sum(n) for the harmonic series.
#The following formula is a good estimate.  np.log is the natural log function from numpy
n=1000000
np.log(n)+0.5772156649+1/(12*n)-1/(112*n*n)<jupyter_output><empty_output>
StarcoderdataJupyterStructuredCleanDedup