Esiste una funzione di conteggio generale correlata alla funzione di conteggio primi?

Question

Esiste una funzione di conteggio generale correlata alla funzione di conteggio primi?

Supponiamo ad esempio che volessi tutti i multipli interi positivi di tre inferiori o uguali a N, esiste una funzione di conteggio di multipli di 3 inferiore o uguale a N?

A volte, potrei desiderare tutti i multipli interi positivi di un prodotto di numeri primi, ad esempio 15, esiste un multiplo positivo di 3 e 5 inferiore o uguale alla funzione di conteggio N?

Answer 1

Solo per espandere il mio commento: se puoi immaginarlo, esiste. Dovrebbe essere ben definito se conta semplicemente se gli interi hanno o meno una proprietà. Puoi vedere qualsiasi funzione di conteggio come la somma cumulativa di una funzione indicatore che è 1 o 0 per ogni numero intero.

Considera una funzione indicatore per la tua proprietà$A$,$\chi_A(n)$. Come hai indicato potresti definire una funzione di conteggio$\pi_A(n)$come [assumendo che siamo interessati a numeri interi strettamente positivi]$$ \pi_A(n) = \sum_{k=1}^n \chi_A(k) $$risultati interessanti relativi a questo includono una funzione generatrice di differenza. Per numeri primi$p_k$, e funzione di conteggio primi$\pi_p(n)$ $$ \sum_{k=p_1}^\infty x^{\pi_p(k)} = \sum_{k=1}^\infty (p_{k+1}-p_k)x^k $$in generale per qualsiasi funzione di conteggio, per i numeri$a_k$, relativo alla condizione$A$ $$ \sum_{k=a_1}^\infty x^{\pi_A(k)} = \sum_{k=1}^\infty (a_{k+1}-a_k)x^k $$ad esempio, la funzione di conteggio dei numeri$\chi_n(n)=1$, dà$\pi_n(n)=n$e$$ \sum_{k=1}^\infty x^{\pi_n(k)} = \sum_{k=1}^\infty (k+1-k)x^k=\frac{x}{1-x} $$in questo caso$\pi_n(n)$è la funzione di conteggio a crescita più rapida ed è linearmente crescente.

Considera la funzione dell'indicatore quadrato$\chi_{\square}(n)$, con condizione$\square(n):\sqrt{n}\in \mathbb{N}$, Poi abbiamo$$ \pi_\square(n) = \sum_{k=1}^n \chi_\square(k) $$poi$$ \sum_{k=1}^\infty x^{\pi_\square(k)} = \sum_{k=1}^\infty ((k+1)^2-k^2)x^k = \frac{3x-x^2 }{(x-1)^2} $$uno dei miei preferiti è$\pi_p(\pi_p(n))$cioè la funzione di conteggio primi nidificata, che si riferisce alla sequenza A073131 as$$ \sum_{k=3}^\infty x^{\pi_p(\pi_p(k))} = \sum_{k=1}^\infty (p_{p_{k+1}} - p_{p_k})x^k $$così possiamo vedere$\pi_p(\pi_p(n))$ conta numeri primi indicizzati primi , come 3, 5, 11, 17, 31, 41, 59, 67, 83, 109,... o A006450 . Possiamo vedere che ogni sequenza intera strettamente crescente avrà una funzione indicatrice, e quindi una funzione di conteggio, e anche una funzione generatrice di differenza. Ad esempio, possiamo nidificare diversi tipi di funzioni di conteggio$$ \sum_{k=3}^\infty x^{\pi_\square(\pi_p(k))} = \sum_{k=1}^\infty (p_{(k+1)^2} - p_{k^2})x^k $$ci dice$\pi_\square(\pi_p(k))$ conta i numeri primi i cui indici sono quadrati , e questo ci insegna che dà una catena generale di composizioni$$ \sum_{k=x}^\infty x^{\pi_{A} \circ \pi_{B} \circ \cdots \pi_{Z} \circ k} = \sum_{k=1}^\infty (z \circ \cdots \circ b \circ a \circ (k+1) - z \circ \cdots \circ b \circ a \circ (k))x^k $$e che anche una composizione di funzioni di conteggio è una funzione di conteggio , perché questa parte di destra è solo una differenza di termini.

I tuoi esempi: i multipli interi positivi di tre vanno come$3,6,9,12,...$, la funzione indicatore potrebbe potenzialmente essere scritta come$$ \chi_{m3}(n) = \bmod(1+2n^2,3) $$la funzione di conteggio associata a questo è$$ \pi_{m3}(n) = \left\lfloor \frac{n}{3} \right\rfloor $$che utilizza la notazione per la funzione floor. Possiamo usare il concetto di annidamento per i multipli di 15, che abbiamo$$ \pi_{m15} = \pi_{m3}(\pi_{m5}(n)) = \pi_{m5}(p_{m3}(n)) = \left\lfloor \frac{\left\lfloor \frac{n}{5} \right\rfloor}{3} \right\rfloor = \left\lfloor \frac{\left\lfloor \frac{n}{3} \right\rfloor}{5} \right\rfloor $$questo dovrebbe contare i numeri divisibili per$5$i cui indici sono divisibili per$3$o vice versa.