← Complete problem index

PROJECT EULER · #0652

Distinct Values of a Proto-logarithmic Function

Statement only · UnsolvedOriginal problem ↗

Consider the values of log2⁡(8), log4⁡(64) and log3⁡(27). All three are equal to 3.

Generally, the function f(m,n)=logm⁡(n) over integers m,n≥2 has the property that
f(m1,n1)=f(m2,n2) if

  1. m1=ae,n1=af,m2=be,n2=bf for some integers a,b,e,f or
  2. m1=ae,n1=be,m2=af,n2=bf for some integers a,b,e,f

We call a function g(m,n) over integers m,n≥2 proto-logarithmic if

  • g(m1,n1)=g(m2,n2) if any integers a,b,e,f fulfilling 1. or 2. can be found
  • and g(m1,n1)≠g(m2,n2) if no integers a,b,e,f fulfilling 1. or 2. can be found.

Let D(N) be the number of distinct values that any proto-logarithmic function g(m,n) attains over 2≤m,n≤N.
For example, D(5)=13, D(10)=69, D(100)=9607 and D(10000)=99959605.

Find D(1018), and give the last 9 digits as answer.


Note: According to the four exponentials conjecture the function logm⁡(n) is proto-logarithmic.
While this conjecture is yet unproven in general, logm⁡(n) can be used to calculate D(N) for small values of N.

Write-up coming later

The complete problem is available here. An approach, code, and answer will be added later.