The following fractions are written on the board 1/n, 2/(n-1), 3/(n-2), ... , n/1 where n is a natural number. Alice calculated the differences of the neighboring fractions in this row and found among them 10000 fractions of type 1/k (with natural k). Prove that he can find even 5000 more of such these differences.
It is weird that Alice is referred to as "he". However, here is what he found.
(2/(n-1))-(1/n)=(2n/(n(n-1)))-((n-1)/(n(n-1)))=(n+1)/(n(n-1))
(3/(n-2))-(2/(n-1))=(3(n-1)/((n-1)(n-2)))-(2(n-2)/((n-1)(n-2)))=((3n-3)/((n-1)(n-2)))-((2n-4)/((n-1)(n-2)))=(n+1)/((n-1)(n-2))
...
((n-1)/2)-(n/1)=((n-1)/2)-(2n/2)=(n+1)/2
These are numbers of the form (n+1)/(x(x-1)) for 2<=x<=n. For (n+1)/(x(x-1)) to be of the form 1/k, n+1 must divide x(x-1). Then, n+1 divides x^2-x, so x^2=x mod n+1. Therefore, the number of fractions of the form 1/k is the number of integers x such that x^2=x mod n+1, 2<=x<=n, which is A087893(n+1).
It seems like all of the terms of A087893 are of the form 2^m-2, where m is the number of distinct prime factors of n. The records are 0, 2, 6, 14, 30, ..., which appear at 2, 6, 30, 210, 2310, ... This looks like the primorials.
2=2
2*3=6
2*3*5=30
2*3*5*7=210
2*3*5*7*11=2310
...
If all terms of A087893 are of the form 2^m-2, then the smallest term above 10000 is 2^14-2=16382. Then, if Alice finds 10000 fractions of the form 1/k, then he can find 6382>5000 more. This first happens when n=(2*3*5*7*11*13*17*19*23*29*31*37*41*43)-1=13082761331670030-1=13082761331670029.
Edited on February 21, 2021, 11:38 am
|
|
Posted by Math Man
on 2021-02-21 11:30:35 |
A boy named Alice
