Given an infinite set $A$ of positive integers, $\min A:=a_0$. For $x\geq a_0$ define $f(x)=xa$, 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_01\}$. 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_01$? If not, what is criterion of existing such frequencies? Do they exist, say, for $A$=primes?

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=11/\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$. 


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. 


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. 

