[Math] the longest terminating (or repeating) decimal created by the division of two natural numbers in which neither number is more than two digits

elementary-number-theorynumber theory

I came across a problem today while teaching in which a long division problem created an unusually long terminating decimal. It intrigued me into more thinking on this.

My question is: What is the longest terminating (or repeating) decimal created by the division of two natural numbers in which neither number is more than two digits? And, is there a way to prove this besides using brute force in trying all possibilities?

Best Answer

The number of digits in the repeat of $\frac 1n$ (larger numerators can only decrease the number of digits) is always a factor of $\phi (n)$, Euler's totient function, the number of numbers less than and coprime to $n$. For primes, $\phi(n)=n-1$, so pjs36's intuition to try large primes is a good one. Once we discover $\frac 1{97}$ has a repeat of $96$ digits, we only need to find that $\phi(98)=42$ and $\phi(99)=60$ and we are done. In fact, the repeat of $\frac 1{98}$ is $42$ decimals, but $\frac 1{99}=0.\overline{01}$

Related Solutions

Project Euler – Problem #25 Solution

The sequence $n \mapsto F_n$ grows exponentially. In fact, I suggest you look at this part of the wikipedia article on Fibonacci numbers, which gives exact and nearly exact formulas for $F_n$ as exponential functions. This should be very helpful in determining the smallest $n$ such that $F_n$ has $1000$ digits.

[Math] Can you answer the son’s fourth-grade homework question: Which numbers are prime, have digits adding to ten and have a three in the tens place

As requested I'm posting this an answer. I wrote a short sage script to check the primality of numbers of the form $10^n+333$ where $n$ is in the range $[4,2000]$. I found that the following values of $n$ give rise to prime numbers:

$$4,5,6,12,53,222,231,416.$$

Edit 3: I stopped my laptop's search between 2000 and 3000, since it hadn't found anything in 20 minutes. I wrote a quick program to check numbers of the form $10^n+3*10^i+33$. Here are a couple

100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000030000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000033
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000300033
100000000000000000000000000000000000000000000000000000300000000000000000000000000000000000000033
100000000000000000000000000000000000000000000000030000000000000000000000000000000000000000000033
100000000000000000000000000000000000000000000030000000000000000000000000000000000000000000000033
10000000000000000000000000000000003000000033
10000000000000000000000000000030000000000033
10000000000000000000000030000000000000000033
10000000003000000000000000000000000000000033

There seemed to be plenty of numbers of this form and presumably I could find more if I checked some of the other possible forms as outlined by dr jimbob.

Note: I revised the post a bit after jimbob pointed out I was actually looking for primes that didn't quite fit the requirements.

Edit 4: As requested here are the sage scripts I used. To check if $10^n+333$ was prime:

for n in range(0,500):
  k=10^n+333
  if(is_prime(k)):
    print n

And to check for numbers of the form $10^n+3*10^i+33$:

for n in range(0,500):
  k=10^n+33
  for i in range(2,n):
    l=k+3*10^i
    if(is_prime(l)):
      print l

Best Answer

Related Solutions

Project Euler – Problem #25 Solution

[Math] Can you answer the son’s fourth-grade homework question: Which numbers are prime, have digits adding to ten and have a three in the tens place

Related Question