The prime Russian mountain.
Patrick Capelle drove my attention to the
f(n) = p(n) mod n
As a matter of fact this function has been
studied as the sequence
A004648. There you can
graph of f(n) provided by E. Labos for the first 50,000
This graph is a kind of tricky because moves to
think -wrongly- that it's a 'continuous' function.
I provide to you some graphs prepared by Capelle
showing the real discontinuous behavior of f(n), for less numbers,
the first: 50,
500, numbers n.
Disregarding the real fact that we are facing a
discontinuous function, it is not very bizarre 'to view' the whole
behavior of this function as sets of points grouped by
ranges inside which the general trend is to climb up to certain
maximum point and then to fall up to 'almost zero' just to start
again a new climbing up trend, in a series of crescendo mountain
sides. This behavior suggested to me the name I have given
to this puzzle.
| Trend #
||n, range (n1, n2)
||f(n), range (f(n1), f(n2))
||and so on
||and so on
1. Can you
explain this general behavior?
Is this behavior a fractal-like one?
In particular can you predict the starting point and the height of
each new 'mountain'?
Capelle thinks that f(n)
cover all the natural numbers. He asks
'Can you prove it or
find a counterexample ?'
Contributions came from Andrew Rupinski, Rudoph Knjzek, Joseph L. Pe,
Anton Brba and Carlos Rivera
I know this answer will be sent by several others, but since the n^th
prime is approximately nlog(n), we have that nlog(n) mod n becomes 0
around when log(n) is an integer. Indeed the first few values of e^d for
d an integer fall within the corresponding ranges shown (for example e^6
~ 403.17 lies in the 6th range). By this crude calculation, we see that
the height of the d^th mountain should also be about e^d since just
before nlog(n) = d*e^d we have that (d*e^d
- k) mod d = e^d - k ~ e^d. Since the n^th prime function is asymptotic
to nlog(n), we see that the behavior of this function should be
fractal-like, namely by zooming out any distance our graph should
resemble the ones shown with the small values clustered and not as
distinguishable but the larger ones spread out to resemble the patterns
To study the general behaviour of f(n) I
use the simple approximation pi(x) = x/log(x)
Now I set x=p(n) and get n=p(n)/log(p(n))
log(p) has an integer and a fractional
f(n)=p(n) mod n f(n)=n*frac(log(p(n)))
If p(n) doesn't grow too fast with n, f(n)
starts again with low values until int(log(p(n))) is incremented.
This happens every time, when log(p(n))=k
with natural number k and I get
p(n)=exp(k) and n=exp(k)/k for the top
values and the starting points of the mountains.
The law is discribed within the answer of
Question 1. Is this fractional-like?
The approximation pi(x)=x/log(x) is not
good enough to predict these values.
Using the proven unequality x/log(x)<pi(x)<1.25506*x/log(x)
for x>=17 I can follow, that there must be one starting point between
n=exp(k)/k and n=exp(1.25506*k)/k with natural number k. These are
large intervals which can hardly be used for a prediction.
This seems to be unprovable.
behavior of f(n) = p(n) mod n is very similar to the behavior of
Round(n ln(n)) mod n since p(n) ~ n ln(n) by the Prime Number Theorem.
graphs of f and F follow the same ascending-descending pattern,
points at which they do so are approximately the same, with the
approximate equality becoming better as n gets large.
explain the ascending-descending behavior of f, it suffices to look
corresponding behavior of F. F(n) = Round(n ln(n)) mod n takes a
value = 0
when Round(n ln(n)) is a multiple of n, i.e., when ln(n) is very
nearly an integer.
fixed positive integer N, let M be such than ln(M) ~ N. Then F ~ 0
near M and F increases
as n is gradually increased, until an integer M1 is reached with
ln(M1) ~ N + 1,
which, again, F ~ 0.
example, ln(150) ~ 5, and we find F ~ 0 near n = 150. As n is
gradually increased, the
F increases until near n = 404, where ln(404) ~ 6 and F ~ 0 again.
Therefore, the "large gaps" in f occur approximately at integers n for
which ln(n) is very
integer, with the approximation becoming better as n gets large.
Indeed, we find
a gap in
f near n = 404, close to where a gap in F also occurs.
above behavior of F (and similarly, of f) can be seen as roughly
fractal since the same regions of
ascent-descent appear on different scales, although no uniform scaling
factor applies to all.
not resolve Question #4, although it seems to me very likely that f
covers the entire set of
In studying the relation
f(n) = p(n) mod n
, one also needs to look at the relationship
g(n) = p’(n)
mod n where p’(n) = 1.13 n lin(n)
which approximates the value of p(n).
I attach the comparative plot of f(n)
and any further comment is superfluous.
As for the specific questions :
1. No, but behaviour is not specific to the prime
2. No, referring to the comparative plot the
function is very repetitive and predictive and has periodic or harmonic
behaviour that can be modelled by simple mathematical formulas.
3. Simple analysis reveals a constant logarithmic
behaviour, thus a general formula can easily be derived
4. Most probably true, i.e. fn(27’067’317)=105
is the first occurrence for f(n)=105,
therefore a large n should be found for
some small f(n).
Interesting is the plot of min[fn(n)] vs. n
which enforces Capelle’s believe
Here are two of the
plots by Anton: f(n) vs g(n);
C. Rivera wrote:
Regarding the Q4. I have not found any n<203280221 (p(n)<4294967291),
such that f(n) is equal to the following values: 330 354 364 378 392 400
Giovanni Resta wrote (22-III-08):
I have extended your search regarding Q4 to all the values f(n)= p(n)
mod n, with f(n)<1000. I've searched up to about n = 1.00366*10^12,
i.e., where p(n) became greater than 30*n.
These f(n) were the last to appear:
f(n) n p(n)
392 1208198739 27788571389
330 1208198749 27788571557
660 1208199077 27788579431
696 1208199097 27788579927
400 55762149197 1505578028719
364 55762149227 1505578029493
Still missing f(n) values below 1000 are 354, 378, 420 and 612.