most recent 30 from http://mathoverflow.net 2013-05-20T20:52:19Z http://mathoverflow.net/feeds/question/41680 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/41680/subtracting-greatest-possible-prime Fedor Petrov 2010-10-10T14:34:20Z 2010-10-10T21:14:02Z

<p>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?</p>

http://mathoverflow.net/questions/41680/subtracting-greatest-possible-prime/41691#41691 Charles 2010-10-10T16:29:53Z 2010-10-10T16:29:53Z

<p>This is Sloane's <a href="http://oeis.org/classic/A121559" rel="nofollow">A121559</a>, which essentially iterates <a href="http://oeis.org/classic/A064722" rel="nofollow">A064722</a>. The behavior is controlled by the (appropriately weighted) distribution of prime gaps below N.</p> <p>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$.</p>

http://mathoverflow.net/questions/41680/subtracting-greatest-possible-prime/41696#41696 Mark Sapir 2010-10-10T17:01:49Z 2010-10-10T17:23:15Z

<p>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. </p>

http://mathoverflow.net/questions/41680/subtracting-greatest-possible-prime/41703#41703 Nikita Sidorov 2010-10-10T18:08:32Z 2010-10-10T18:08:32Z

<p>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). </p> <p>If $A$ grows subexponentially, this is usually not good news for the ``ergodic'' questions like this. </p>