Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given an infinite set $A$ of positive integers, $\min A:=a_0$. For $x\geq a_0$ define $f(x)=x-a$, where $a\leq x$, $a\in A$ is greatest possible. Then for positive integer $x$ iterations $x$, $f(x)$, $f(f(x))$, $\dots$ finally come to some element of the set $\{0,1,\dots,a_0-1\}$. Denote this final number $F(x)$. For example, if $A$ is the set of primes, $F(x)$ equals either 0 or 1. Do there always exist frequencies $\lim \frac{|F^{-1}(s)\cap [1,N]|}{N}$ for $s=0,1,\dots,a_0-1$? If not, what is criterion of existing such frequencies? Do they exist, say, for $A$=primes?

share|improve this question
sorry? I do not see typos –  Fedor Petrov Oct 10 '10 at 20:24
ah, ok my dictionaries claim that substraction is also ok (see for example answers.com/topic/substraction) –  Fedor Petrov Oct 10 '10 at 21:11
That dictionary marks it [Obs.] (obsolete), which means it's not used in modern works. –  Charles Oct 10 '10 at 21:16

3 Answers 3

This is Sloane's A121559, which essentially iterates A064722. The behavior is controlled by the (appropriately weighted) distribution of prime gaps below N.

Heuristically, with $\ell=1-1/\log N$, you'd expect something like $(1-\ell)\left(1+\ell^3+\ell^5+\ell^7+\ell^{11}+\cdots\right)$ 1s below N, where the exponents are 1 less than the locations of the 1s. You can stop the sum around $\log^2 N$.

share|improve this answer
+1 for finding it in Sloane. –  Gerry Myerson Oct 11 '10 at 2:56

It is easy to construct $A$ for which the limit does not exist. Consider the following set $A$. Include all even numbers in the intervals $[10^n, 10^{n+1}]$ for even $n=0,2,...$, and all numbers divisible by 3 in the intervals $(10^n,10^{n+1})$ for odd $n$. Now if $N=10^k$ with $k$ even then the probability of 0 is $\ge .9$, and if $k$ is odd, then the probability of $1$ is $\ge .9*1/3=.3$. In general, the limit exists if the intervals between consecutive numbers in $A$ are "uniformly spaced". In particular, if $A$ is a set of primes, I do not know how to show that the limit exists. It may be a hard number theory problem. For example, we know (Green and Tao) that the set of primes contains arbitrary long arithmetic progressions, but it is not clear (to me) how often these occur and how often progressions start at relatively small numbers and are relatively long.

share|improve this answer
Thanks, the question about arbitrary $A$ was indeed naive. But which information do we really need about differences of neighbour terms? Specification of this question is the case of primes. –  Fedor Petrov Oct 10 '10 at 17:29
I guess you need to consider the probability of 1 for a number below $a_n$, the $n$-th number in $A$. Assume that $a_{n+1}/a_n$ is always $\lt 2$ (as in the case of primes). Then the probability of $1$, $p(a_{n+1})$, is the probability that your number is $\lt a_n$ times $p(a_n)$ plus the probability that your number is $\gt a_n$ times $p(a_{n+1}-a_n)$. This gives some sort of recurrent equation. –  Mark Sapir Oct 10 '10 at 18:05
I suspect that modulo RH the limit exists and the probability of 1 is about .65... (an empirical calculation for $N=5*10^7$). I do not know whether known, weaker than RH, statements would suffice. I hope that specialists in number theory can help. –  Mark Sapir Oct 10 '10 at 18:35
@Mark: Did you mean the probability of 0? The probability of 1 is clearly at most 1/2. –  Charles Oct 10 '10 at 19:10
@Charles: Why $1/2$? –  Mark Sapir Oct 10 '10 at 19:13

If I understand you correctly, this is effectively the question about (greedy) systems of numeration for the natural numbers. These are well understood in the case when $A$ satisfies some recurrence relation -- like the Fibonacci sequence (Zeckendorf) or the denominators $q_n$ of the CF convergents for some irrational $\alpha$ (Ostrowski).

If $A$ grows subexponentially, this is usually not good news for the ``ergodic'' questions like this.

share|improve this answer
Would you please give more details and references? –  Mark Sapir Oct 10 '10 at 18:26
Off the top of my head: A. Fraenkel, Systems of numeration, Amer. Math. Monthly 92 (1985), 105–114. P. Grabner, P. Liardet and R. Tichy, Odometers and systems of numeration, Acta Arith. 80 (1995), 103–123. My own survey paper (maths.manchester.ac.uk/~nikita/ad.pdf) may be also somewhat useful, though it is mostly about systems of numeration for the reals and vectors rather than the integers. –  Nikita Sidorov Oct 10 '10 at 18:42
yes, exactly, that's greedy representation of $x$ as a sum of primes (in general setting, of elements of $A$) thanks for your links! –  Fedor Petrov Oct 10 '10 at 18:51
Sure, no problem. –  Nikita Sidorov Oct 10 '10 at 19:02

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.