Growth of a certain function $f(x) = 2^x - \sum_{n=1}^{2^x} g(n)$

Question

Growth of a certain function $f(x) = 2^x - \sum_{n=1}^{2^x} g(n)$

where $g(n)$ is equal $1$ if $gcd(A, n) \neq 1$ or $gcd(B, n) \neq 1$ for some const $A$ and $B$ (and $gcd(A, B) = 1$).

otherwise $g(n)$ is equal to $0$.

for example for $A = 2$ and $B = 3$ we have:

First column: $x$.

Second column: $2^x$.

Thrid column: $f(x) = 2^x - \sum_{n=1}^{2^x} g(n)$.

Fourth column: $\frac{f(x)}{2^x}$.

 6           64                    22  [0.34375000000000000000]
 7          128                    44  [0.34375000000000000000]
 8          256                    86  [0.33593750000000000000]
 9          512                   172  [0.33593750000000000000]
10         1024                   342  [0.33398437500000000000]
11         2048                   684  [0.33398437500000000000]
12         4096                  1366  [0.33349609375000000000]
13         8192                  2732  [0.33349609375000000000]
14        16384                  5462  [0.33337402343750000000]
15        32768                 10924  [0.33337402343750000000]
16        65536                 21846  [0.33334350585937500000]
17       131072                 43692  [0.33334350585937500000]
18       262144                 87382  [0.33333587646484375000]
19       524288                174764  [0.33333587646484375000]
20      1048576                349526  [0.33333396911621093750]
21      2097152                699052  [0.33333396911621093750]
22      4194304               1398102  [0.33333349227905273438]
23      8388608               2796204  [0.33333349227905273438]
24     16777216               5592406  [0.33333337306976318359]
25     33554432              11184812  [0.33333337306976318359]
26     67108864              22369622  [0.33333334326744079590]
27    134217728              44739244  [0.33333334326744079590]
28    268435456              89478486  [0.33333333581686019897]
29    536870912             178956972  [0.33333333581686019897]
30   1073741824             357913942  [0.33333333395421504974]

for example for $A = 127$ and $B = 521$ we have:

 6           64                    64  [1.00000000000000000000]
 7          128                   127  [0.99218750000000000000]
 8          256                   254  [0.99218750000000000000]
 9          512                   508  [0.99218750000000000000]
10         1024                  1015  [0.99121093750000000000]
11         2048                  2029  [0.99072265625000000000]
12         4096                  4057  [0.99047851562500000000]
13         8192                  8113  [0.99035644531250000000]
14        16384                 16224  [0.99023437500000000000]
15        32768                 32448  [0.99023437500000000000]
16        65536                 64895  [0.99021911621093750000]
17       131072                129790  [0.99021911621093750000]
18       262144                259580  [0.99021911621093750000]
19       524288                519161  [0.99022102355957031250]
20      1048576               1038323  [0.99022197723388671875]
21      2097152               2076645  [0.99022150039672851562]
22      4194304               4153291  [0.99022173881530761719]
23      8388608               8306582  [0.99022173881530761719]
24     16777216              16613164  [0.99022173881530761719]
25     33554432              33226328  [0.99022173881530761719]
26     67108864              66452655  [0.99022172391414642334]
27    134217728             132905309  [0.99022171646356582642]
28    268435456             265810616  [0.99022170901298522949]
29    536870912             531621233  [0.99022171087563037872]
30   1073741824            1063242467  [0.99022171180695295334]

My observations show that it does not grow exponentially:

$\lim_{x\to\infty} \frac{f(x)}{2^x} = 0$

Can someone help to prove that this is a polynomial or is it an exponential function?

Is there an idea?

For a good understanding of the problem, I include the source code (C):

#include <stdio.h>

unsigned long long int gcd ( unsigned long long int a, unsigned long long int b )
{
  unsigned long long int c;
  while ( a != 0 ) {
     c = a; a = b%a;  b = c;
  }
  return b;
}

int main()
{

    unsigned long long int n = 6;
    unsigned long long int max;

    for(max=64; max < 1073741825; max*=2)
    {
        unsigned long long int counter_gcd = 0;

        unsigned long long int i;
        for(i=2; i < max; i++)
        {
            if( gcd(i, 2) != 1 || gcd(i, 3) != 1 )
                counter_gcd++;
        }

        printf("%2Ld %12Ld  %20Ld  [%.20Lf]\n", n, max, max-counter_gcd, (max-counter_gcd) / (long double) max);

        n++;

    }

    return 0;
}

Answer 1

We can rewrite $f(x)$ as $$\sum_{n=1}^{2^x} (1-g(n))$$ and $1-g(n)=0$ if $n$ has a common factor with $A$ or $B$, and otherwise $1-g(n)=1$.

So we have that $f(x)$ counts the $n\leq 2^x$ that are relative prime to $AB$. This is approximately:

$$\left\lfloor \frac{2^x\phi(AB)}{AB}\right\rfloor$$

Where $\phi$ is Euler's totient function.

In the case when $A,B$ are prime, it is exactly:

$$2^x-\left\lfloor \frac {2^x}{A} \right \rfloor - \left\lfloor \frac {2^x}{B} \right \rfloor + \left\lfloor \frac {2^x}{AB} \right \rfloor$$

But an exact answer is harder without general $A,B$. If $p_1,\cdots,p_k$ are all the prime divisors of $AB$ then the exact value is:

$$2^x-\sum_{j=1}^{k} (-1)^{j-1}\sum_{1\leq i_1<i_2<\cdots<i_j\leq k} \left\lfloor \frac{2^x}{p_{i_1}\cdots p_{i_j}}\right\rfloor=\sum_{d\mid AB}\mu(d)\left\lfloor\frac{2^x}{d}\right\rfloor$$

This is an inclusion-exclusion formula.

I get when $x=6,A=2,B=3,$ I got $f(x)=21$. That's because your $C$ program skips $i=1$, aka $n=1.$

But you'll find the $$\lim_{x\to\infty}\frac{f(x)}{2^x}=\frac{\phi(AB)}{AB}=\left(1-\frac1{p_1}\right)\left(1-\frac1{p_2}\right)\cdots \left(1-\frac1{p_k}\right).$$ In the case of $A=2,B=3$ this is $\frac{1}{2}\cdot\frac{2}{3}=\frac{1}{3}$ and for $A=127,B=521$ (both prime) it is $\frac{126}{127}\cdot\frac{520}{521}\approx 0.9902217117$.