All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Arithmetic Derivative (Posted on 2022-06-10) Difficulty: 4 of 5
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)

No Solution Yet Submitted by Larry    
Rating: 5.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Python version for 1 & 2 | Comment 5 of 7 |
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

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (10)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information