5
$\begingroup$

I suggest that you read the conclusion at the bottom, before reading this entire and very long post.

Let $x=\frac{p}{q} \in [\frac{1}{2},\frac{3}{4}]$ be a rational number, with $p, q$ integers. Also, let $x_1=x$ and $x_{n+1}=f(x_{n})$ for some specific function $f$ to be discussed later. Let $p_n$ be the proportion of binary digits of $x_n$ that are equal to $1$.

Is there an absolute maximum number $N$, not depending on $x$, possibly as low as $N=3$, for which the following is true: at least one the $p_k$'s, with $1\leq k\leq N$, is equal to $\frac{1}{2}$. For many $x$'s it will be $p_1$, for some other $x$'s, it will be $p_2$, and for the remaining $x$'s, it will be $p_3$. (that's the conjecture)

The table below shows the approximated proportions $p_1,\cdots,p_7$ for various $p$ and $q$. The first two columns represent $p$ and $q$. It was computed based on the first $129$ binary digits. Of course, if $q$ is a power of $2$, my conjecture is not correct: this case must be excluded. I used $f(x) = 4x(1-x)$ which is the logistic map.

710 1310    49.6%   49.6%   47.3%   57.4%   51.9%   48.8%   45.0%
710 1311    48.1%   51.2%   51.9%   50.4%   48.8%   56.6%   47.3%
710 1312    49.6%   58.1%   43.4%   54.3%   51.9%   51.2%   50.4%
710 1313    55.0%   54.3%   41.1%   45.7%   43.4%   55.8%   43.4%
710 1314    44.2%   48.1%   51.9%   52.7%   48.8%   53.5%   41.9%
710 1315    55.0%   49.6%   50.4%   49.6%   48.1%   50.4%   48.1%
710 1316    50.4%   54.3%   46.5%   48.1%   48.1%   49.6%   38.0%
710 1317    43.4%   48.8%   38.0%   51.9%   59.7%   57.4%   52.7%
710 1318    51.2%   54.3%   41.9%   52.7%   51.2%   54.3%   48.8%
710 1319    49.6%   57.4%   56.6%   55.8%   47.3%   49.6%   53.5%
710 1320    49.6%   43.4%   52.7%   49.6%   51.2%   41.1%   42.6%
710 1321    49.6%   52.7%   49.6%   50.4%   53.5%   48.8%   51.2%
710 1322    53.5%   54.3%   51.2%   51.2%   47.3%   58.1%   57.4%
710 1323    48.8%   58.9%   51.9%   51.9%   51.9%   53.5%   46.5%
710 1324    48.8%   52.7%   56.6%   50.4%   43.4%   51.9%   48.1%
710 1325    49.6%   54.3%   51.9%   46.5%   46.5%   55.0%   54.3%
710 1326    45.0%   55.0%   44.2%   46.5%   48.1%   47.3%   50.4%
710 1327    48.1%   51.9%   43.4%   47.3%   45.7%   50.4%   51.9%
710 1328    46.5%   58.9%   50.4%   43.4%   47.3%   44.2%   48.8%
710 1329    49.6%   60.5%   47.3%   50.4%   41.9%   55.0%   55.0%
711 1310    47.3%   51.2%   48.8%   48.8%   56.6%   55.0%   47.3%
711 1311    48.8%   48.1%   45.7%   43.4%   48.8%   55.0%   53.5%
711 1312    49.6%   48.1%   44.2%   50.4%   41.9%   48.8%   45.0%
711 1313    45.0%   50.4%   46.5%   45.7%   51.9%   48.1%   51.9%
711 1314    33.3%   51.2%   51.2%   51.2%   49.6%   49.6%   48.1%
711 1315    55.0%   57.4%   51.2%   51.9%   46.5%   55.8%   55.0%
711 1316    48.8%   55.0%   48.8%   48.8%   47.3%   51.2%   51.2%
711 1317    49.6%   53.5%   54.3%   48.1%   53.5%   53.5%   54.3%
711 1318    45.0%   55.8%   43.4%   45.0%   44.2%   45.7%   56.6%
711 1319    53.5%   59.7%   48.1%   51.9%   55.8%   51.2%   52.7%
711 1320    40.3%   54.3%   52.7%   52.7%   47.3%   45.7%   54.3%
711 1321    49.6%   52.7%   48.1%   51.9%   44.2%   50.4%   49.6%
711 1322    53.5%   48.8%   39.5%   48.1%   61.2%   45.7%   54.3%
711 1323    47.3%   49.6%   52.7%   48.8%   45.7%   48.8%   51.2%
711 1324    48.8%   58.9%   52.7%   56.6%   48.1%   56.6%   49.6%
711 1325    48.1%   51.9%   43.4%   50.4%   42.6%   49.6%   43.4%
711 1326    29.5%   55.8%   41.9%   49.6%   51.2%   58.9%   43.4%
711 1327    51.2%   58.1%   44.2%   48.1%   50.4%   51.2%   42.6%
711 1328    51.2%   56.6%   45.7%   49.6%   52.7%   45.7%   51.9%
711 1329    48.1%   49.6%   52.7%   51.9%   55.8%   51.2%   48.1%
712 1310    43.4%   55.8%   49.6%   48.8%   56.6%   53.5%   48.1%
712 1311    53.5%   55.8%   49.6%   43.4%   51.9%   56.6%   48.1%
712 1312    49.6%   51.2%   44.2%   50.4%   45.7%   48.1%   45.7%
712 1313    52.7%   56.6%   47.3%   45.0%   50.4%   48.8%   52.7%
712 1314    49.6%   55.0%   52.7%   53.5%   49.6%   49.6%   41.9%
712 1315    40.3%   49.6%   50.4%   49.6%   56.6%   48.8%   59.7%
712 1316    49.6%   58.1%   46.5%   48.1%   52.7%   48.1%   51.2%
712 1317    53.5%   51.9%   48.1%   50.4%   50.4%   48.8%   49.6%
712 1318    49.6%   44.2%   52.7%   47.3%   43.4%   50.4%   46.5%
712 1319    46.5%   47.3%   56.6%   44.2%   51.9%   45.0%   48.8%
712 1320    44.2%   54.3%   48.8%   49.6%   45.7%   41.9%   45.0%
712 1321    49.6%   51.2%   48.1%   53.5%   48.8%   50.4%   47.3%
712 1322    55.8%   55.8%   34.1%   50.4%   46.5%   52.7%   51.9%
712 1323    49.6%   55.8%   60.5%   48.8%   46.5%   51.2%   50.4%
712 1324    49.6%   47.3%   48.8%   49.6%   47.3%   49.6%   53.5%
712 1325    55.0%   51.9%   48.8%   52.7%   49.6%   45.0%   52.7%
712 1326    45.0%   49.6%   44.2%   52.7%   53.5%   48.1%   49.6%
712 1327    45.0%   61.2%   45.0%   53.5%   51.2%   51.2%   51.2%
712 1328    47.3%   55.0%   47.3%   45.7%   53.5%   53.5%   51.2%
712 1329    45.0%   51.2%   52.7%   51.2%   40.3%   57.4%   49.6%
713 1310    47.3%   49.6%   51.9%   57.4%   47.3%   58.9%   50.4%
713 1311    49.6%   46.5%   55.8%   56.6%   51.9%   48.1%   43.4%
713 1312    49.6%   51.2%   55.8%   51.2%   46.5%   47.3%   54.3%
713 1313    50.4%   54.3%   48.8%   49.6%   45.0%   58.9%   46.5%
713 1314    38.8%   61.2%   58.9%   44.2%   54.3%   57.4%   50.4%
713 1315    45.7%   56.6%   48.1%   54.3%   51.2%   48.1%   55.0%
713 1316    52.7%   56.6%   49.6%   47.3%   46.5%   49.6%   50.4%
713 1317    43.4%   55.0%   54.3%   51.9%   48.1%   45.7%   55.0%
713 1318    42.6%   58.1%   48.8%   51.9%   46.5%   48.8%   55.0%
713 1319    52.7%   49.6%   48.8%   55.8%   43.4%   58.9%   50.4%
713 1320    53.5%   45.7%   56.6%   45.7%   51.9%   59.7%   48.1%
713 1321    48.8%   55.0%   47.3%   47.3%   50.4%   52.7%   48.1%
713 1322    45.7%   52.7%   40.3%   51.2%   46.5%   45.7%   53.5%
713 1323    48.8%   49.6%   52.7%   46.5%   50.4%   50.4%   49.6%
713 1324    49.6%   48.1%   48.8%   51.9%   49.6%   40.3%   53.5%
713 1325    45.0%   51.9%   41.1%   51.2%   51.9%   54.3%   44.2%
713 1326    41.9%   48.8%   45.7%   48.8%   47.3%   45.0%   45.0%
713 1327    42.6%   48.8%   55.0%   48.1%   57.4%   55.8%   48.8%
713 1328    51.9%   51.9%   48.8%   48.1%   55.8%   54.3%   50.4%
713 1329    49.6%   53.5%   48.1%   54.3%   55.8%   50.4%   46.5%
714 1310    51.9%   51.9%   51.9%   54.3%   55.8%   52.7%   42.6%
714 1311    46.5%   55.8%   38.8%   51.2%   45.0%   54.3%   50.4%
714 1312    49.6%   51.2%   53.5%   49.6%   57.4%   56.6%   53.5%
714 1313    48.1%   39.5%   50.4%   46.5%   52.7%   49.6%   47.3%
714 1314    49.6%   52.7%   44.2%   53.5%   51.9%   52.7%   50.4%
714 1315    58.1%   41.9%   49.6%   38.8%   48.8%   53.5%   49.6%
714 1316    40.3%   41.1%   46.5%   44.2%   55.8%   48.8%   51.2%
714 1317    49.6%   51.2%   54.3%   45.7%   59.7%   50.4%   55.8%
714 1318    48.1%   57.4%   48.1%   46.5%   51.2%   47.3%   50.4%
714 1319    51.9%   46.5%   56.6%   48.8%   51.2%   59.7%   49.6%
714 1320    39.5%   54.3%   46.5%   51.9%   49.6%   54.3%   48.8%
714 1321    48.8%   53.5%   45.7%   48.8%   58.9%   51.2%   48.1%
714 1322    45.0%   53.5%   47.3%   48.1%   54.3%   51.2%   48.1%
714 1323    33.3%   50.4%   49.6%   51.9%   42.6%   48.8%   41.9%
714 1324    48.8%   53.5%   49.6%   45.0%   54.3%   56.6%   46.5%
714 1325    49.6%   52.7%   42.6%   51.9%   50.4%   55.0%   54.3%
714 1326    49.6%   50.4%   41.9%   47.3%   50.4%   44.2%   55.0%
714 1327    55.0%   51.2%   55.8%   42.6%   51.2%   52.7%   50.4%
714 1328    46.5%   51.9%   53.5%   47.3%   47.3%   58.1%   50.4%
714 1329    47.3%   48.8%   48.8%   49.6%   48.8%   55.0%   50.4%
715 1310    51.2%   48.1%   51.9%   51.9%   55.0%   47.3%   45.7%
715 1311    51.9%   47.3%   41.9%   46.5%   32.6%   55.8%   48.1%
715 1312    50.4%   48.1%   42.6%   46.5%   53.5%   56.6%   56.6%
715 1313    53.5%   56.6%   52.7%   52.7%   58.1%   42.6%   57.4%
715 1314    44.2%   42.6%   52.7%   52.7%   38.8%   51.9%   47.3%
715 1315    44.2%   41.1%   53.5%   47.3%   51.9%   42.6%   49.6%
715 1316    49.6%   47.3%   40.3%   51.2%   53.5%   53.5%   41.9%
715 1317    47.3%   51.2%   46.5%   40.3%   45.7%   44.2%   54.3%
715 1318    51.2%   53.5%   48.8%   53.5%   48.8%   55.0%   46.5%
715 1319    49.6%   51.2%   48.8%   57.4%   53.5%   52.7%   50.4%
715 1320    49.6%   51.9%   49.6%   46.5%   47.3%   48.1%   49.6%
715 1321    49.6%   56.6%   55.8%   49.6%   45.0%   47.3%   48.1%
715 1322    46.5%   53.5%   45.0%   45.0%   52.7%   50.4%   44.2%
715 1323    49.6%   49.6%   52.7%   49.6%   51.2%   50.4%   48.8%
715 1324    48.8%   53.5%   51.2%   51.2%   54.3%   55.0%   45.0%
715 1325    48.8%   50.4%   40.3%   51.2%   58.1%   51.2%   55.0%
715 1326    25.6%   50.4%   48.1%   48.8%   41.9%   53.5%   48.8%
715 1327    53.5%   49.6%   48.1%   48.8%   54.3%   56.6%   48.8%
715 1328    47.3%   58.1%   49.6%   47.3%   48.8%   49.6%   47.3%
715 1329    46.5%   51.2%   51.9%   43.4%   49.6%   51.2%   44.2%
716 1310    42.6%   48.8%   52.7%   46.5%   51.9%   56.6%   48.1%
716 1311    50.4%   55.0%   46.5%   48.8%   45.0%   52.7%   47.3%
716 1312    50.4%   47.3%   47.3%   48.1%   52.7%   58.9%   45.0%
716 1313    54.3%   49.6%   45.7%   43.4%   51.2%   45.7%   51.2%
716 1314    60.5%   58.1%   52.7%   50.4%   51.9%   53.5%   42.6%
716 1315    45.7%   55.0%   46.5%   47.3%   56.6%   50.4%   51.2%
716 1316    48.1%   50.4%   54.3%   46.5%   58.9%   41.9%   47.3%
716 1317    59.7%   58.1%   46.5%   43.4%   54.3%   53.5%   54.3%
716 1318    41.1%   56.6%   48.8%   44.2%   55.0%   58.9%   49.6%
716 1319    49.6%   59.7%   46.5%   48.8%   42.6%   55.0%   51.2%
716 1320    45.0%   48.1%   48.8%   51.2%   49.6%   50.4%   59.7%
716 1321    49.6%   51.2%   51.9%   51.9%   50.4%   51.2%   48.8%
716 1322    45.0%   49.6%   51.2%   49.6%   46.5%   46.5%   45.0%
716 1323    50.4%   53.5%   51.9%   51.2%   47.3%   47.3%   50.4%
716 1324    48.8%   57.4%   50.4%   43.4%   56.6%   53.5%   52.7%
716 1325    53.5%   54.3%   51.2%   49.6%   51.9%   49.6%   55.0%
716 1326    52.7%   55.0%   44.2%   39.5%   56.6%   52.7%   45.0%
716 1327    48.8%   48.8%   55.8%   54.3%   46.5%   55.8%   46.5%
716 1328    48.1%   56.6%   56.6%   46.5%   43.4%   52.7%   58.9%
716 1329    51.2%   57.4%   51.9%   53.5%   46.5%   49.6%   58.1%
717 1310    45.7%   49.6%   52.7%   48.8%   47.3%   49.6%   51.2%
717 1311    46.5%   61.2%   51.9%   48.8%   50.4%   59.7%   47.3%
717 1312    50.4%   52.7%   41.1%   43.4%   45.0%   41.9%   47.3%
717 1313    57.4%   51.9%   49.6%   45.0%   52.7%   55.8%   50.4%
717 1314    38.8%   54.3%   48.1%   50.4%   45.7%   50.4%   54.3%
717 1315    48.8%   58.1%   46.5%   41.9%   45.7%   51.2%   48.8%
717 1316    49.6%   52.7%   47.3%   52.7%   51.9%   48.1%   48.1%
717 1317    52.7%   60.5%   42.6%   48.8%   54.3%   57.4%   45.7%
717 1318    45.0%   43.4%   56.6%   68.2%   53.5%   48.1%   48.8%
717 1319    51.2%   52.7%   45.7%   54.3%   53.5%   43.4%   48.1%
717 1320    58.9%   51.9%   55.0%   49.6%   51.2%   44.2%   42.6%
717 1321    49.6%   55.8%   46.5%   47.3%   49.6%   58.1%   45.7%
717 1322    44.2%   49.6%   45.7%   41.9%   48.1%   52.7%   56.6%
717 1323    49.6%   50.4%   45.0%   58.9%   49.6%   55.0%   55.0%
717 1324    49.6%   48.1%   50.4%   49.6%   50.4%   41.9%   47.3%
717 1325    51.9%   45.7%   46.5%   46.5%   50.4%   51.9%   45.7%
717 1326    45.0%   60.5%   49.6%   51.2%   58.9%   55.0%   45.0%
717 1327    48.1%   62.0%   41.9%   55.8%   53.5%   49.6%   51.2%
717 1328    46.5%   56.6%   51.9%   56.6%   44.2%   55.0%   57.4%
717 1329    48.8%   50.4%   54.3%   51.2%   49.6%   52.7%   53.5%
718 1310    48.1%   54.3%   54.3%   48.1%   52.7%   56.6%   52.7%
718 1311    47.3%   50.4%   40.3%   52.7%   45.7%   57.4%   51.2%
718 1312    48.8%   48.8%   47.3%   42.6%   51.2%   59.7%   51.2%
718 1313    48.8%   48.8%   43.4%   40.3%   41.1%   53.5%   52.7%
718 1314    49.6%   57.4%   44.2%   51.2%   50.4%   48.1%   55.0%
718 1315    53.5%   55.8%   46.5%   48.8%   48.8%   49.6%   48.8%
718 1316    49.6%   50.4%   44.2%   41.1%   45.7%   56.6%   51.2%
718 1317    48.1%   56.6%   48.8%   45.7%   45.0%   51.9%   43.4%
718 1318    48.8%   51.2%   44.2%   50.4%   51.2%   53.5%   52.7%
718 1319    56.6%   53.5%   48.8%   50.4%   56.6%   50.4%   50.4%
718 1320    63.6%   55.8%   45.0%   46.5%   55.0%   53.5%   46.5%
718 1321    49.6%   53.5%   54.3%   50.4%   53.5%   47.3%   48.1%
718 1322    54.3%   50.4%   50.4%   51.9%   54.3%   58.1%   50.4%
718 1323    49.6%   55.0%   51.2%   51.9%   56.6%   50.4%   46.5%
718 1324    49.6%   55.0%   50.4%   51.2%   54.3%   46.5%   45.0%
718 1325    43.4%   48.8%   42.6%   56.6%   51.9%   51.2%   50.4%
718 1326    53.5%   57.4%   55.0%   51.2%   48.8%   55.8%   49.6%
718 1327    50.4%   55.0%   41.1%   48.8%   54.3%   62.8%   45.7%
718 1328    46.5%   56.6%   53.5%   47.3%   50.4%   55.0%   43.4%
718 1329    53.5%   53.5%   47.3%   57.4%   51.9%   48.1%   51.2%
719 1310    46.5%   52.7%   51.2%   58.1%   57.4%   54.3%   47.3%
719 1311    54.3%   51.9%   48.8%   51.2%   54.3%   45.0%   39.5%
719 1312    48.8%   52.7%   53.5%   46.5%   46.5%   51.2%   37.2%
719 1313    47.3%   52.7%   42.6%   55.8%   52.7%   57.4%   45.7%
719 1314    27.9%   49.6%   44.2%   47.3%   50.4%   50.4%   51.9%
719 1315    54.3%   49.6%   41.9%   43.4%   58.1%   52.7%   51.2%
719 1316    50.4%   42.6%   51.9%   41.9%   42.6%   48.8%   48.8%
719 1317    51.9%   52.7%   51.9%   45.7%   46.5%   47.3%   52.7%
719 1318    58.1%   46.5%   47.3%   48.8%   48.1%   47.3%   42.6%
719 1319    51.9%   47.3%   45.0%   42.6%   47.3%   46.5%   48.8%
719 1320    45.0%   51.2%   51.9%   50.4%   51.2%   48.1%   49.6%
719 1321    49.6%   56.6%   48.1%   55.8%   53.5%   54.3%   57.4%
719 1322    45.0%   45.0%   49.6%   48.1%   58.1%   59.7%   54.3%
719 1323    49.6%   48.8%   48.1%   48.1%   53.5%   45.0%   45.7%
719 1324    49.6%   49.6%   44.2%   47.3%   52.7%   47.3%   51.9%
719 1325    55.8%   48.8%   49.6%   56.6%   50.4%   52.7%   41.1%
719 1326    53.5%   58.9%   48.1%   52.7%   51.2%   49.6%   51.9%
719 1327    48.8%   57.4%   50.4%   42.6%   63.6%   51.2%   55.0%
719 1328    46.5%   58.1%   51.9%   48.1%   48.8%   52.7%   45.0%
719 1329    47.3%   52.7%   42.6%   48.8%   43.4%   55.8%   50.4%

1. Background

The immense majority of irrational numbers have $p_1=\frac{1}{2}$, but this is not the case for rational numbers. If my conjecture is true for rational numbers (with the exclusion previously discussed), then the next step is to see if it is true for all real numbers. If it is also true for all real numbers (say with $N=3$), then we would have this spectacular result:

The binary digits of either $\sqrt{2}$ or $5\sqrt{2}$ (or both) are 50/50 zeroes and ones.

The explanation is as follows:

Take $x=x_1=\frac{\sqrt{2}}{2}$. Then $x_2=2\sqrt{2}-2$ and $x_3=8(5\sqrt{2}-7)$. At least one of these three numbers have 50/50 zeroes and ones in their binary expansion, assuming my conjecture is correct.

If this fails with $f$ being the logistic map, is there another function $f$ for which my conjecture is more likely to be true? If you look at my table, a number that might fail is $\frac{718}{1320}$ though you would need to look at the full periods of $x_1, x_2, x_3$ to get the exact $p_1, p_2, p_3$, not just look at the first $129$ digits. Note that $1320$ has many divisors.

Another way to look at my question is to identify which rational numbers have 50/50 zeroes and ones in their binary expansion. Of course, this can only happen to rational numbers having an even period.

2. Choosing a function $f$ that could work

If $q$ is not a prime resulting in an even period, we may have a problem. For instance, both $x=\frac{7}{15}$ and $x=\frac{4}{21}$ result in $p_1, p_2$ different from $\frac{1}{2}$. If instead of the logistic map, you use $f(x)=\frac{x}{x+1}$ then $p_2=\frac{1}{2}$ in both of these cases. The issue could be: how fast do you fall back on a denominator that is a prime resulting in an even period, after successive iterations $x_1,x_2$ and so on. How many iterations are needed? It is not sure if $N$ is bounded.

Also, with $f(x) = \frac{x}{x+1}$ we have $x_n\rightarrow 0$, though this might not be a problem. To the contrary, the logistic map creates a sequence $\{x_n\}$ that is dense in $[0, 1]$ for almost all $x_1$.

Another mapping worth investigating, similar to the logistic map as it creates a sequence that is dense in $[0, 1]$, is $f(x) = bx-\lfloor bx\rfloor$, where $b \in ]1, 2[$ is a rational number. As with the logistic map, if $x=x_1$ is rational, then all $x_n$'s are rational. The brackets stand for the integer part function. With this particular mapping, with $b=\frac{3}{2}$, if $x=\frac{7}{15}$ then $p_2 =\frac{1}{2}$. But if $x=\frac{4}{21}$, then none of $p_1, p_2, p_3$ is equal to $\frac{1}{2}$.

There are many other mappings worth investigating, for instance $f(x)=x+\frac{1}{x} - \lfloor x+\frac{1}{x} \rfloor$.

3. Choosing $f$ such that $\{x_n\}$ converges

Here I mean convergence to a value $x_{\infty} > 0$, and preferably to a well known irrational mathematical constant. A simple example is $f(x) = \frac{1}{1+x}$. In this case, $x_\infty = \frac{-1+\sqrt{5}}{2}$ yet all $x_n$'s are rational if $x_1$ is rational. The limit is a number widely believed to have 50/50 zeroes and ones in its binary expansion (indeed, a normal number.)

With this choice, $p_2=\frac{1}{2}$ both for $x_1= \frac{7}{8}$ and $x_1 = \frac{4}{21}$. It also leads to an interesting observation: $p_n\rightarrow\frac{1}{2}$ thus successive $x_n$'s, have $p_n$'s that (on average) get closer and closer to $\frac{1}{2}$. I would expect that many of the $p_n$'s are exactly $\frac{1}{2}$ regardless of $x_1$. Also, if you start with $x_1=\frac{1}{2}$, then $x_n = \frac{F_{n+1}}{F_{n+2}}$ is a ratio of two successive Fibonacci numbers.

Note: Here are dealing with two different definitions for the proportion of digits equal to $1$:

  • For rational numbers, the proportion is computed on the period, which always consists of a finite number of digits. The proportion always exists and can be computed explicitly, in all cases.
  • For irrational numbers, the proportion is first defined on the first $M$ digits, then the exact proportion is the limit as $M\rightarrow\infty$. For some very rare yet infinitely many non-normal numbers, that limit (and thus the proportion of binary digits equal to $1$) may not exist. An example of such number is the following: the first digit is $1$, the next $2^1$ digits are $0$, the next $2^2$ digits are $1$, the next $2^3$ digits are $0$ and so on.

4. Examples

Here are a few examples. I will add more, all are with $f(x) = \frac{1}{1+x}$. So, regardless of $x$, we have $p_\infty=\frac{1}{2}$. Also, $x_n$ can be computed efficiently: the numerator and denominator obey the same recurrence relationship as Fibonacci numbers.

  • $x= \frac{603}{1046} \Rightarrow p_1 =\frac{1}{2}$ (exact value.) The period of $x_1=x$ has $522$ digits. You can find the period (with all the digits) using WolframAlpha, see here. Thus, in this case, no need to look at $x_2, x_3$ and so on.
  • $x=\frac{1}{91} \Rightarrow p_5 =\frac{1}{2}, x_5=\frac{275}{458}$. However, none of $p_1, p_2, p_3,p_4$ is $\frac{1}{2}$. Note that $458 = 2\times 229$, with $229$ being a prime, and $2$ being a power of $2$. None of $x_1, x_2, x_3, x_4$ has that structure, $x_5$ is the first one. In addition the period of $x_5$ is even: its length is $76 = \frac{1}{3}(229-1)$. As a result, it has $38$ zeroes and $38$ ones ($38=\frac{76}{2}$), thus $p_5=\frac{38}{76}=\frac{1}{2}$.This means that with this function $f$, $N$ must be larger or equal to $5$.
  • I looked at all $x=\frac{p}{q}$ with $p\in \{1,2,3,4\}$ and $q\in \{5,6,\cdots,124\}$. It does seem that for all but two of them, $N\leq 8$. The exception is $x=\frac{2}{89}$, and possibly $\frac{1}{63}$.For the latter, $x_6=\frac{509}{827}$ and WolframAlpha was unable to give me the period: it may or may not have $p_6=\frac{1}{2}$, and if not, it's pretty close. Note that if $q$ is a power of $2$, it is not a problem with this particular $f$. I suspect with this $f$, some other types of fractions could lead to a systemic failure and must be excluded. The results obtained so far are somewhat encouraging and surprising, but would love to check with much larger $p$'s and $q$'s.
  • I looked at all $x=\frac{p}{q}$, with $n\leq 10$ and $p\in \{5000,5001,5002\}$ and $q\in \{8901,\cdots,8998\}$. I found a $p_k$ equal to $\frac{1}{2}$, with $k\leq 10$, for each of them it seems. The one I am a little unsure about is $x=\frac{5001}{8946}$, for which $x_5=\frac{36840}{59773}$ and $p_5$ is very well approximated by $\frac{1}{2}$, but I don't know if $p_5=\frac{1}{2}$. In short, bigger $p,q$ seem to behave better. If there are some $x$'s causing issues, it seems it would be for small values of $p$ and $q$. Quite encouraging!

5. Additional properties and comments

Unless otherwise specified, I also use $f(x) = \frac{1}{1+x}$ here.

Properties

  1. Recurrence relations. Let $x_n = \frac{a_n}{b_n}$, with $a_1=p, > b_1=q$. Then $a_{n+1} = b_n$ and $b_{n+1} = a_n + b_n$. More generally, for any $x$ rational or not, we have $x_n=(F_{n-2}x + > F_{n-1})/(F_{n-1}x+F_n)$ if $n\geq 2$, where $F_0=0, F_1=1, F_2=1$ and so on are the Fibonacci numbers, and $x=x_1$. This is trivial.
  2. On certain types of primes. Let $x_n = \frac{A_n}{B_n}$ with $A_n, B_n$ co-primes. If $B_n = 2^r \cdot d^s$ with $r\geq 0, s\geq 1$ being integers, and $d$ is a prime belonging to the sequence A014662, then $p_n=\frac{1}{2}$. To the contrary, if $d$ belongs to the complementary prime sequence A014663, then $p_n \neq \frac{1}{2}$. The density of primes in A014662 is $\frac{17}{7}$ times higher than that in A014663. More generally, if $B_n$ has one or more distinct prime factors belonging to A014663 and none from A014662, then $p_n \neq \frac{1}{2}$. If $B_n$ has two or more distinct prime factors belonging to A014662 and none from A014663, then sometimes $p_n=\frac{1}{2}$, sometimes not: for instance, if $B_n \in \{33,57,65,95 \}$ then $p_n=\frac{1}{2}$; if $B_n \in \{15,55,39,51\}$ the opposite is true. I am still looking at the most general case where $B_n$ is any integer. For instance, if $B_n=77 = 7 \times 11$ with $7$ in A014663 and $11$ in A014662, we have $p_n=\frac{1}{2}$. The largest prime factor must belong to A014662 for this to be possible, and this is the case here.

Note 1: Rather than using $x_{n+1}=f(x)$, we could use a more elaborate scheme working as follows, based on two functions $f(x), g(x)$:

  • We start at iteration $1$ with $x=x_1$ also denoted as $x_{1,1}$.

  • At iteration $2$, we generate two new numbers: $x_{2,1}=f(x_{1,1})$ and $x_{2,2}=g(x_{1,1})$.

  • At iteration $3$, we generate four new numbers: $x_{3,1}=f(x_{2,1})$, $x_{3,2}=f(x_{2,2})$, $x_{3,3}=g(x_{2,1})$ and $x_{3,4}=g(x_{2,2})$.

  • And so on.

We define $p_n$ as the value closest to $\frac{1}{2}$, computed on $x_{n,1}, x_{n,2},\cdots, x_{n,d_n}$ with $d_n = 2^{n-1}$. In case of ties, pick the value that is $\geq \frac{1}{2}$.

This way, with appropriate choices for $f$ and $g$, we are far more likely to make a correct conjecture: the fact that there is $N$ (possibly $N\leq 5$) such that regardless of $x$, at least one of the $p_n$'s with $1\leq n \leq N$, is always equal to $\frac{1}{2}$. Of course $p_n$ depends on $x$, but the deep result with potentially big implications, is that $N$ does not depend on $x$, or more precisely, that there is a finite upper bound $N$ that works for all $x$.

Note 2: As an illustration, consider this. Let $x=0.1001000100001...$. This is a non-normal irrational number with $p_1=0$. Yet $p_4 =\frac{1}{2}$ it seems (still a conjecture at this point). The same could apply to $x=\pi-3$ (believed to be normal): we might not be able to prove that $p_1=\frac{1}{2}$, but maybe we could be able to say this: at least one of $x_1=\pi -3$, $x_2=\frac{1}{\pi-2}$, $x_3=\frac{\pi-2}{\pi-1},\cdots, x_N$ has $p_k=\frac{1}{2}$ ($k\leq N$). This would be a huge breakthrough, even though we would not be able to explicitly name a single $k$ that works. We might not even know $N$, other than the fact that it is finite. At least, this is the final purpose of this research. We are still a very very long shot away from proving this!

6. Conclusions

While we focused exclusively on rational numbers, the end goal here is to try to prove the normality of classic mathematical constants such as $\pi, e,\log 2,\sqrt{2}$ and so on. In this post, I believe that I established a new path to achieve this goal. Future steps include:

  • Getting a complete solution, with proof, for property #2 in section 5.
  • Finding $f$ (or $f, g$ as described in the note in section 5) such that we can identify a universal constant $N$ that works for all
    rational $x$, or at least prove that such a finite constant exists.
    This is the hardest part. The function $f(x) = \frac{1}{1+x}$ might just work.
  • Generalize this to irrational numbers: this should be easy, as irrationals can be arbitrarily approximated by rationals.

Then we might be able to issue the following theorem, with proof:

Theorem

For any real number $x$, one of the following numbers $x_n$, with $1\leq n \leq N$ (with $N$ not depending on $x$, and finite) has exactly 50% of its binary digits equal to one:

$$x_n =\frac{F_{n-2}x + F_{n-1}}{F_{n-1}x+F_n} \mbox{ if } n\geq 2, \mbox{ with } x_1=x.$$

Here $F_n$ is the $n$-th Fibonacci number ($F_0=1, F_1=1, F_2=1$ and so on.)

The proof will involve deep results about prime numbers.

$\endgroup$
12
  • 3
    $\begingroup$ @joriki No, because the figures are (not very good) estimates based on just the first $129$ bits of the expansion. The first number in the list, $\ \frac{71}{131}\ $, for example, has a binary expansion of period $\ 130 \ $. The sequence of bits in one period are those of the binary expansion of $\ 71\times\left(\frac{2^{130}-1}{131}\right)\ $, which contains exactly $65$ zeroes and $65$ ones. Since the last bit of a period is a one, the percentage of ones in the first $129$ bits is $\ 100\times\frac{64}{129}\approx 49.61\%\ $. $\endgroup$ – lonza leggiera Jan 18 '20 at 11:25
  • 1
    $\begingroup$ If $\ N\ $ exists for $\ f(x)=4x(1-x)\ $, it must be at least $4$. For $\ \frac{p}{q}=\frac{5}{7}=0.\overline{101}_2\ $, $\ p_1=\frac{2}{3}\ $, $\ p_2=\frac{11}{21}\ $, $\ p_3= \frac{515}{1029}\ $. For $\ i=1,2,3\ $, we have $\ p_i=\frac{\lambda\left(7^{2i-1}\right)-2}{\lambda\left(7^{2i-1}\right)}\ $, where $\ \lambda\ $ is the Carmichael function. If this pattern continues for all $\ i\ $, then $\ N\ $ doesn't exist for this $\ f\ $. $\endgroup$ – lonza leggiera Jan 18 '20 at 21:33
  • 1
    $\begingroup$ The period of $\ \frac{509}{827}\ $ is $826$, and contains $413$ of each binary digit. In general, if the denominator of a proper fraction in its lowest terms is $\ q=2^r(2d+1)\ $, then the period of its binary expansion is the multiplicative order of $2$ in the group of integers relatively prime to $\ 2d+1\ $ modulo $\ 2d+1\ $. It must be a divisor of $\ \lambda(2d+1)\ $. The expansion will also have an initial segment of length $\ r\ $ which lies outside the periodic part. $\endgroup$ – lonza leggiera Jan 18 '20 at 22:54
  • 4
    $\begingroup$ Your question is a mess, please stop with those kind of posts, you are supposed to know that a question must be readable, simple and clear. Nobody cares of your "conjectures". The only idea in there is to look at the iterates of $f(x)=4x(1-x)$ and given $a$ seek if the proportion of 1's in the binary expansion of $f^{(k)}(a)$ is $1/2$ for some $k\le K$. $\endgroup$ – reuns Jan 19 '20 at 9:52
  • 1
    $\begingroup$ @Reuns: I believe you or anyone can vote to close it if you don't like it. My interest is in the advancement of math, not in writing elegantly. Style is just a distraction/pursuit that would keep me away from my goal. I'm not looking for fame here, it's enough if only one person (me) is interested in what I write, I don't ask for more than that. $\endgroup$ – Vincent Granville Jan 19 '20 at 14:57
0
$\begingroup$

The main issue here is that looking at the full period, even if all the $x(n)$'s had exactly 50/50 zeroes and ones in their period, is useless and counter-productive. Sure, you are approaching $\frac{-1+\sqrt{5}}{2}$ by numbers such as $$x(n) = \frac{F_{n-1} p + F_n q}{F_{n-1} p + F_{n+1} q}$$ where the $F_n$'s are Fibonacci numbers, and in many instances (these instances becoming more and more rare as $n\rightarrow\infty)$ the period of $x(n)$ has the same number of $0$'s and $1$'s. But the period of $x(n)$, with its length denoted here as $L(n)$, grows exponentially fast on average, while the accuracy (number of correct digits in base $2$ at each iteration) grows linearly. Even if focusing on large $n$'s with the smallest possible period, these minimum periods grow more slowly than exponentially, but much faster than linearly.

The solution consists of looking at the proportion of $0$'s and $1$'s in the first $c\log L(n)$ digits of the period of $x(n)$, ($c$ is a constant) and show that it tends to $\frac{1}{2}$.

Let me illustrate this on one example. The successive approximations of $1/7$ in base $5$ are:

0 / 5
3 / 25
17 / 125
89 / 625
446 / 3,125
2,232 / 15,625
11,160 / 78,125
55,803 / 390,625
279,017 / 1,953,125
1,395,089 / 9,765,625
6,975,446 / 48,828,125
34,877,232 / 244,140,625
174,386,160 / 1,220,703,125
871,930,803 / 6,103,515,625
4,359,654,017 / 30,517,578,125
21,798,270,089 / 152,587,890,625
108,991,350,446 / 762,939,453,125
544,956,752,232 / 3,814,697,265,625
2,724,783,761,160 / 19,073,486,328,125
13,623,918,805,803 / 95,367,431,640,625
68,119,594,029,017 / 476,837,158,203,125

The period for these fractions, when expressed in base $2$, starting with $n=1$, is $4\cdot 5^n$, always. Also, all these fractions have the exact same number of zeros and ones in their period, in base $2$. You might be tempted to conclude that $\frac{1}{7}$ thus must have 50% ones in its binary expansion. Yet in base $2$, the number $\frac{1}{7}$ is equal to

$$0.001001001001001001001001001001001001001001...$$

To see what happens, look at the last number in the above table, that is
$$68,119,594,029,017 / 476,837,158,203,125$$ In base $2$, its representation is

0.001001001001001001001001001001001001001001001000101000110000101100101101011100011110010011111011100101...

The first $47$ binary digits match those of $\frac{1}{7}$ but it fails at position $48$. Yet that number has exactly $2\cdot 5^{21}$ ones and $2\cdot 5^{21}$ zeroes in its period of length $L=4\cdot 5^{21}$. Looking at the full period yields an erroneous conclusions, while if look only at the first $\log_2 L \approx 51$ digits, you end up with the correct conclusion: the proportion of ones in the binary expansion of $\frac{1}{7}$ is around $1/3$. As $n\rightarrow\infty$, you will notice that it tends to $\frac{1}{3}$, and this is the correct answer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.