Infinitude and asymptotic growth of a sparse recursively generated prime sequence
问题内容
Construction of the set: Start with an empty set F.Test primes in sequential order.A prime P is called "foundational" and belongs to F if and only if it is NOT representable as $$x_1 q_1^{a_1}+x_2 q_2^{a_2}+...+x_n q_n^{a_n}$$ Where ${q_1 ,q_2, q_3,...,q_n}$ are earlier primes of the set F and are distinct, $x_1,x_2,\dots\in\{0,1\}$ and $a_n\ge 1$ for all n.Also note that each foundational prime contributes at most one term.
According to the definition above, start with first prime $2$.Now as the set F is empty $2$ is admitted to the set F.Now to check whether $3$ belongs to F, we have to check whether the equation $2^a =3$ possess any integral solution such that $a \ge\ 1$.As this equation doesn't possess any integral solution $3$ is admitted.The next prime is $5$.But $2^1 +3^1 = 5$, so $5$ is not admitted to the set.Continuing this way, I have computed $15$ terms of this sequence using SageMath: $$\{2,3,23,37,47,61,223,233,743,1237,11813,39209,518057,3131537,7810427,…\}$$
The gap sequence is $$\{1,20,14,10,14,162,10,510,494,10576,27396,478848,2613480,4678890,…\}$$ The gap sequence is behaving erractically.As far as i could tell by heuristics is that this subsequence of primes is very sparse.
The closest sequence I could find to this $A034875$.But there are some significant differences between these two.First, this sequence is prime only.Second, this sequence don't admit exponent $0$.There are other distinctions too.
Open Questions:
- Is this sequence finite?
- What is the asymptotic growth of this sequence?
- How this sequence is connected to the density of primes?
Also the sum: $$\sum_{n=1}^{15}\frac{1}{f_n} \approx 0.95$$Looking at how sparse the sequence it's strongly possible that this sum is bounded below $1$.
Any insights,comments or observations are much appreciated.
回答 (1)
Given a set of numbers $\{p_1, p_2, \dots, p_k\}$, let's count how many numbers less than or equal to $N$ can be formed via your sum.
We only need to consider powers $p_i^{\alpha_i}$ with $p_i^{\alpha_i}\leq N$, that is, $\alpha_i\leq\frac{\ln N}{\ln p_i}$.
There are $\lfloor\frac{\ln N}{\ln p_i}+1\rfloor$ choices for each summand, this gives a total of at most $$\prod_{i=1}^k\left(\frac{\ln N}{\ln p_i}+1\right)=\prod_{i=1}^k\left(\frac{\ln (p_iN)}{\ln p_i}\right)$$ sums equalling at most $N$.
This increases as $O(\ln(N)^k)$.
However, the number of primes $\pi(N)$ below $N$ increases as $O(N / \ln(N))$. Therefore, there exist some $N$ for which $\pi(N)$ is strictly greater than $\prod_{i=1}^k\left(\frac{\ln (p_iN)}{\ln p_i}\right)$.
It follows that the sequence of foundational primes is an infinite sequence.