Let $A$ be a set 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 the maximal possible. Then for a positive integer $x$ the 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 by $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 a criterion of existing of such frequencies? Do they exist, say, for $A$=primes?
$\begingroup$
$\endgroup$
3
asked Oct 10, 2010 at 14:34
-
$\begingroup$ sorry? I do not see typos $\endgroup$– Fedor PetrovCommented Oct 10, 2010 at 20:24
-
$\begingroup$ ah, ok my dictionaries claim that substraction is also ok (see for example answers.com/topic/substraction) $\endgroup$– Fedor PetrovCommented Oct 10, 2010 at 21:11
-
1$\begingroup$ That dictionary marks it [Obs.] (obsolete), which means it's not used in modern works. $\endgroup$– CharlesCommented Oct 10, 2010 at 21:16
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
13
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.
-
$\begingroup$ 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. $\endgroup$ Commented Oct 10, 2010 at 17:29
-
$\begingroup$ 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. $\endgroup$– user6976Commented Oct 10, 2010 at 18:05
-
$\begingroup$ 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. $\endgroup$– user6976Commented Oct 10, 2010 at 18:35
-
$\begingroup$ @Mark: Did you mean the probability of 0? The probability of 1 is clearly at most 1/2. $\endgroup$– CharlesCommented Oct 10, 2010 at 19:10
-
$\begingroup$ @Charles: Why $1/2$? $\endgroup$– user6976Commented Oct 10, 2010 at 19:13
$\begingroup$
$\endgroup$
1
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)$ $1$s below $N,$ where the exponents are $1$ less than the locations of the $1$s. You can stop the sum around $\log^2 N$.
-
2$\begingroup$ +1 for finding it in Sloane. $\endgroup$ Commented Oct 11, 2010 at 2:56
$\begingroup$
$\endgroup$
4
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.
answered Oct 10, 2010 at 18:08
-
$\begingroup$ Would you please give more details and references? $\endgroup$– user6976Commented Oct 10, 2010 at 18:26
-
$\begingroup$ 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. $\endgroup$ Commented Oct 10, 2010 at 18:42
-
$\begingroup$ yes, exactly, that's greedy representation of $x$ as a sum of primes (in general setting, of elements of $A$) thanks for your links! $\endgroup$ Commented Oct 10, 2010 at 18:51
-