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?
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
9
3
|
|
|||||||||||
|
|
4
|
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$. |
|||||
|
You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.
|
4
|
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. |
|||||||||||||||
|
|
2
|
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. |
||||||||||||
|
