Consider the following (simplified) definition of the "Arithmetic Derivative" for n in positive integers:
D(0) = D(1) = 0
D(prime) = 1
D(ab) = D(a)*b + D(b)*a
Examples:
D(7) = 1 because 7 is prime.
D(30) = D(5*6) = D(5)*6 + 5*D(6) = 1*6 + 5*D(2*3)
= 6 + 5*[D(2)*3+2*D(3)] = 6 + 5*5 = 31, so ...
D(30) = 31
D(58) = 31 (More than one integer can have the same Arithmetic Derivative.)
(1). Find n and D(n) (n up to 5 digits) such that D(n) is the largest.
(2). Find n and D(n) (n up to 5 digits and not prime) such that the ratio D(n)/n is the largest.
(3). Which 4-digit Palindrome is the Arithmetic Derivative of the most 4-digit positive integers, and list them.
(4). For what set of n is n = D(n)
That faulty prime check mentioned earlier really cost me in time. I had it checking d instead of i as being prime; but d is a whole array (vector or list), and as the numbers grew larger the progress became excruciatingly slow. It had me wondering if Python would have been faster, but the real speed up was correcting the bug.
But it still had me thinking and I rewrote most of it in Python. Python doesn't have a factor() function to get the prime factors of a number, so I wrote one. The rewrite in Python is:
def factor(n):
global tmp
answ=[]
tmp=(n)
addends=[4,2,4,2,4,6,2,6]
def divn(dvr):
global tmp
while tmp%(dvr)==0:
answ.append(dvr)
tmp=tmp//dvr
divn(2)
divn(3)
divn(5)
d=(7)
while (d)*(d)<=tmp:
for i in range(8):
divn(d)
d=d+(addends[i])
if tmp>1:
answ.append(tmp)
return answ
upto=99999
d=[0,0]
for i in range(2,upto):
f=factor(i)
f1=f[0]
f2=i//f1
d.append(f1*d[f2]+f2)
largest=0; largei=[]
for i in range(2,upto):
if d[i]>=largest:
if d[i]>largest:
largei=[i]
else:
largei.append(i)
largest=d[i]
print(largest,largei)
largest=0; largei=[]
for i in range(2,upto):
if d[i]>1:
if d[i]/i>=largest:
if d[i]>largest:
largei=[i]
else:
largei.append(i)
largest=d[i]/i
print(largest,d[largei[0]],largei)
the output:
770048 [98304]
8.0 524288 [65536]
being the answers to (1) and (2)
Edited on June 10, 2022, 2:51 pm
|
|
Posted by Charlie
on 2022-06-10 14:47:36 |
Python version for 1 & 2
