Problem of the Month (May 2001)

This month we feature a number theory problem sent to me by Thomas Kantke. Starting with a natural number n≥2, we want to reach 2 by iterating one of the three steps:

1) subtract 1
2) add 1
3) divide by an integer factor which is no larger than its square root

For example, 2001 ⇒ 2000 ⇒ 80 ⇒ 16 ⇒ 4 ⇒ 2 is the fastest way to reduce 2001 to 2.

Several questions arrise. For a given n, how many steps f(n) does it take to reach 2? What are the smallest s(k) and largest l(k) numbers which require k steps to get to 2? For a given n, what is the minimum number F(n) of additions/subtractions that produces 2? What are the smallest S(k) and largest L(k) numbers which require k additions/subtractions? Are S(k) and L(k) even defined for large values of k? In particular, are there any numbers for which F(n)=5? What is the limiting density of numbers that require k additions/subtractions?

ANSWERS

Joseph DeVincentis, Ulrich Schimke, and Brendan Owen found that l(k)=2^{2^k}, since the most we can decrease a number at each step is to take its square root.

All of the above computed small values of s(k). Joseph DeVincentis gave the following data for k≤9, and Berend van der Zwaag extended it for n≥10:

Values of s(k)

k	1	2	3	4	5	6	7	8	9	10	11	12
s(k)	3	5	7	14	38	172	823	6185	87223	1940494	373943587	>1200000000

Joseph DeVincentis also gives the following data on S(k) (though S(4) comes from Thomas Kantke and the bound for S(5) comes from Berend van der Zwaag):

Values of S(k)

k	1	2	3	4	5
S(k)	3	19	173	3976733	>1200000000

Ulrich Schimke found this classification of those numbers with F(n)=0: Let p(1)^a(1)p(2)^a(2)... p(k)^a(k) where p(i) < p(i+1) are primes. Then F(n) = 0 iff p(1)=2 and for every m = 2,..,k we have p(1)^a(1)p(2)^a(2)... p(m–1)^a(m–1) > p(m).

Ulrich Schimke also showed that there are infinitely many integers with F(n) = 0 (like 2^k) and infinitely many integers with F(n)=1 (like 2^k+1). Thomas Kantke proved that there are infinitely many integers with F(n)=2 (since there are infintely many primes of the form 24n+5). Are there infinitely many integers for which F(n)=3? Are there any for which F(n)=5?

Joseph DeVincentis has this to say about finding numbers n for which F(n) is large: One tactic that might work is to develop large lists of numbers with the next smaller F, searching multiples of any prime found to have that F to build the lists quickly. When you find two even numbers two apart with that F, test the number between them. Of course, this might not find the smallest number with the desired F first, and at some point you have to be checking all numbers (or at least all primes) to generate one of the lists of numbers with a given F.

Brendan Owen notes that some numbers have many ways to reach 2 the fastest. For example, 35 has 5 ways of getting to 2 in 4 steps, and 576 has 20 ways of getting to 2 in 4 steps.

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 7/1/09.