A little number theoretic game

Question

I came up with this little two player game:

The players take turns naming a positive integer. When one player says the number $n$, the other player can only reply in two different ways: They can either respond with $n+1$ or they can divide $n$ by a prime number if the division works out (without a remainder). Who says the number 1 wins.

Example game:

A	B
48	24
25	26
27	9
10	2
1

A wins.

A round of this game could be infinite, if both players always reply with $n+1$, but with reasonable play (both players trying to win), each round is finite: Assume that the one player just said the number $n$. We argue that the sequence will reach a number strictly smaller than $n$ after at most $n$ steps. Note that it suffices that within the next $n$ steps, one player chooses to divide by a prime at least once to immediately reach a number smaller than $n$. By Bertrand's Postulate, there is a prime number $p$ with $n \leq p < 2n$. So within the first $n$ steps of the game, either one player divides by a prime, in which case the result is strictly smaller than $n$, or $p$ is reached. But if $p$ is reached, the only reasonable play is to answer "1", since this wins the game.

Thus, the sequence will always reach 1 eventually. Since it is a finite perfect information game with no draws, there is always a winning strategy for one of the two players. The following numbers are winning numbers, i.e. the player that says one of these numbers can force a win.

1, 4, 6, 10, 14, 16, 22, 25, 27, 34, 36, 38, 40, 46, 49, 51, 56, 58, 60, 63, 65, 69, 74, 77, 82, 84, 86, 88, ….

This sequence does not seem to be on OEIS, I will suggest an entry for it soon.

I wrote a program to generate winning numbers up to 10000, an I noticed that the gaps between winning numbers are relatively small and relatively constant. Approximately one third of the numbers are winning numbers and the difference between two winning numbers is often 2, 3 or 4.

I think the set of winning numbers poses some interesing questions, so just for fun:

• Is there an absolute bound for the gap between two consecutive winning numbers?
• Does the density of this set converge? If so, what is the value?
• Is there an easy way to see whether a number is winning?
• What is the computational complexity of determining whether a given number is winning?
• Is there a simple winning strategy that a human can remember, or is it just chaos?

I would be interested in your thoughts, and maybe you also have some answers to other interesting questions that I did not ask.

EDIT: This sequence is now on OEIS: A362416.

Answer 1

(This is not an answer, but an extensive comment and numerical simulation about Grundy values.)

I believe there is some level of confusion because there are actually two very similar games under discussion: in what I propose to call the original game, the moves from any $n>1$ are to $n+1$ and $n/p$ with $p$ a prime factor of $n$, whereas in the modified game (suggested in the comments to the question), the only move from a prime $p$ is to $1$ (in both cases, there are no move from $1$, making whoever reaches $1$ first the winner).

The original game is not well-founded, so it conceivably has drawing positions, but as proved in the original question, there are actually no such positions; the modiified game, however, is well-founded. Furthermore, the P (=second player wins) and N (=first player wins) positions for both games coincide, so we can treat them as identical insofar as studying the P/N positions go. However, this remark does not extend to the Grundy function (nim value, or whatever you might want to call it): in the modified game, the Grundy value of any prime number is $1$ by definition; in the original game, there is no reason for this to be the case.

It is not clear a priori that the Grundy value is always finite/meaningful in the original game, because it has a loopy component: while it was proved in the question that $G$ is never a draw under perfect play, I don't see an obvious reason why $G + (*n)$ might not be a draw. For explanations as to what Grundy values mean in the case of loopy game, I refer to A. Siegel, Combinatorial Game Theory (2013), definition IV.4.12 (not exactly applicable here because the game isn't finite either, but if we believe figure 4.7 in the definition it doesn't matter). The gist of the matter is that $G$ is said to have Grundy value $n$ iff $G + (*n)$ (meaning the disjunctive sum of $G$ and a single nim heap with $n$ sticks) is a second-player win (viꝫ. is a P position): so long as all options of $G$ have a finite Grundy value, it is also the case that $G$ does, and the Grundy value of $G$ is then given by the mex (=smallest excluded) of the Grundy values of the options; when this is the case, $G + (*n)$ also have a finite Grundy value, given by the nim sum as usual. Loopy games can conceivably have non-finite Grundy values (which Siegel writes $\infty(S)$ where $S$ is a set), but experimentally this does not occur for the game being discussed here. (I don't have a proof. Of course I'm talking about the original game here, because in the case of the modified game, this issue doesn't arise at all.)

The following Sage code computes the Grundy value of the position $n$ in either the original or the modified game according to the value of the variable modified_game (the computation is straightforward after noting the fact that P-positions have Grundy value 0, even in loopy games; the fact that the code terminates proves that the computed value is finite):

# Compute the Grundy function of the following game: from n>1 we can
# move to either n+1 or n/p where p is a prime factor of n (and n=1
# there are no legal moves: whoever reaches 1 first wins the game).

# See <URL:
# https://mathoverflow.net/questions/445015/a-little-number-theoretic-game
# > for context and discussion.

# Set the following to False for the original game, and True for the
# variant where the only allowed move from p prime is to move to 1
# (i.e., win).
modified_game = False
# Warning: Be sure to clear cache_grundy if this is changed!

# Return list of possible moves from n, in sorted order
def moves(n):
    if n==1:
        return []
    return sorted([n+1] + [n/p for (p,_) in factor(n)])

cache_pn = {}
def compute_pn(n):
    # Return True if the position is P or False if it is N
    if n in cache_pn: return cache_pn[n]
    if modified_game and is_prime(n):
        # This shouldn't change anything:
        cache_pn[n]=False
        return False
    for k in moves(n):
        if compute_pn(k):
            # We have a P option: the position is N
            cache_pn[n]=False
            return False
    # Every option is N: the position is P
    cache_pn[n]=True
    return True

cache_grundy = {}
def compute_grundy(n):
    # Return the Grundy value of the position n
    if n in cache_grundy: return cache_grundy[n]
    if compute_pn(n):
        # We treat P positions as a special case to avoid looping
        # forever (note that even for loopy games, the Grundy value of
        # a second-player win is unambiguously 0).
        cache_grundy[n] = 0
        return 0
    if modified_game and is_prime(n):
        # In the modified game, prime numbers have Grundy value 1 by definition
        cache_grundy[n]=1
        return 1
    # Compute the set of excluded values:
    excl = set()
    for k in moves(n):
        excl.add(compute_grundy(k))
    # Now return its mex:
    for v in range(len(excl)+1):
        if not v in excl:
            cache_grundy[n] = v
            return v
    raise Exception("this should not happen")

The first Grundy values for the original game, starting with 1 are: 0, 2, 1, 0, 1, 0, 2, 1, 2, 0, 1, 2, 1, 0, 2, 0, 2, 1, 2, 1, 3, 0, 1, 3, 0, 3, 0, 1, 2, 1.

The corresponding values for the modified game are as follows: 0, 1, 1, 0, 1, 0, 1, 1, 2, 0, 1, 2, 1, 0, 2, 0, 1, 3, 1, 1, 2, 0, 1, 3, 0, 2, 0, 2, 1, 3.

The first P positions for either game are: 1, 4, 6, 10, 14, 16, 22, 25, 27, 34, 36, 38, 40, 46, 49, 51, 56, 58, 60, 63, 65, 69, 74, 77, 82, 84, 86, 88, 91, 94, 96, 100, 104, 106, 111, 115, 117, 119, 121, 123, 129, 132, 134, 136, 140, 142, 144, 146, 150, 152.

The first positions having the following Grundy values in the original game are: 0: 1; 1: 3; 2: 2; 3: 21; 4: 78; 5: 5538; 6: 138600. No position up to $10^7$ has Grundy value greater than 6. Edit: the number 32110722 ($2 × 3^3 × 7 × 17 × 19 × 263$) is the first with Grundy value 7.

The corresponding values for the modified game are: 0: 1; 1: 2; 2: 9; 3: 18; 4: 364; 5: 1260; 6: 108108. No position up to $10^7$ has Grundy value greater than 6. Edit: the number 23129820 ($2^2 × 3^3 × 5 × 7 × 29 × 211$) is the first with Grundy value 7.

The tally of positions among the first $10^7$ having the following Grundy values in the original game are: 0: 3261996; 2: 2030150; 1: 3203496; 3: 1224407; 4: 258511; 5: 21142; 6: 297.

The tally of positions among the first $10^7$ having the following Grundy values in the modified game are: 0: 3261996; 1: 3390181; 2: 1978115; 3: 1105840; 4: 242523; 5: 20995; 6: 349.

(So the discrepancy between the counts found by I. J. Kennedy and Peter Taylor is explained by the fact that one was considering the original game and one was considering the modified game. I hope this clears up the confusion!)

Update (2023-04-21): Besides the Grundy value, I think it's also interesting to consider the “game duration” (I don't know the standard term for this), namely the number of moves in the game if the winning player tries to win as fast as possible while the losing player tries to lose as slowly as possible. This is defined inductively by: $$ \begin{aligned} \operatorname{duration}(G) &= 0\text{ if $G$ is terminal}\\ \operatorname{duration}(G) &= \max\{\operatorname{duration}(G')+1 : G'\text{ option of }G\}\\ &\text{ if $G$ is a P-position}\\ \operatorname{duration}(G) &= \min\{\operatorname{duration}(G')+1 : G'\text{ a P-option of }G\}\\ &\text{ if $G$ is an N-position}\\ \end{aligned} $$ and Sage code computing it is as follows (continuing the code already written above):

cache_duration = {}
def compute_duration(n):
    # Return the game duration of the position n (where the losing
    # player tries to make the game last for as long as possible
    # whereas the winning player tries to end it as soon as possible).
    if n in cache_duration: return cache_duration[n]
    if n==1:
        cache_duration[n]=0
        return 0
    if is_prime(n):
        cache_duration[n]=1
        return 1
    if compute_pn(n):
        # We are the losing player: try to delay!
        vals = [compute_duration(k)+1 for k in moves(n)]
        dur = max(vals)
        cache_duration[n] = dur
        return dur
    else:
        # We are the winning player: try to end!
        vals = [compute_duration(k)+1 for k in moves(n) if compute_pn(k)]
        dur = min(vals)
        cache_duration[n] = dur
        return dur

(clearly this is the same for the original game and for the modified game since from a prime position the player will immediately move to 1 and terminate the game). Note that the game duration thus defined is even for P-positions and odd for N-positions, so it contains the information of which player is winning.

The first duration values for the game, starting with 1 are: 0, 1, 1, 2, 1, 2, 1, 3, 3, 2, 1, 3, 1, 6, 5, 4, 1, 3, 1, 3, 3, 2, 1, 7, 6, 5, 4, 3, 1, 3, 1, 5, 7, 6, 5, 4, 1, 6, 5, 4, 1, 3, 1, 3, 3, 2, 1, 5, 4, 3.

The first positions having the following durations in the game are: 0: 1; 1: 2; 2: 4; 3: 8; 4: 16; 5: 15; 6: 14; 7: 24; 8: 74; 9: 93; 10: 142; 11: 141; 12: 140; 13: 622; 14: 745; 15: 1204; 16: 1203; 17: 1202; 18: 1935; 19: 1934; 20: 7216; 21: 7215; 22: 7214; 23: 12847; 24: 21643; 25: 33539; 26: 86611; 27: 86610; 28: 86609; 29: 281331; 30: 281330; 31: 449631; 32: 562675; 33: 562674; 34: 1221050; 35: 2517976; 36: 2517975; 37: 5845198; 38: 8439912; 39: 8439911; 40: 8439910.

The tally of positions among the first $10^7$ having the following durations in the game are: 0: 1; 1: 664579; 2: 30657; 3: 629716; 4: 206897; 5: 1205915; 6: 378438; 7: 1318956; 8: 680231; 9: 1200304; 10: 779015; 11: 818601; 12: 572977; 13: 467615; 14: 324556; 15: 237032; 16: 161209; 17: 110655; 18: 73592; 19: 49266; 20: 32225; 21: 20968; 22: 13227; 23: 8755; 24: 5537; 25: 3515; 26: 2192; 27: 1420; 28: 825; 29: 476; 30: 285; 31: 153; 32: 91; 33: 51; 34: 30; 35: 22; 36: 9; 37: 3; 38: 1; 39: 1; 40: 1.

For example, here's how the game unfolds starting from 8439910 (in 40 moves):

A: 8439911; B: 8439912; A: 8439913; B: 8439914; A: 4219957; B: 4219958; A: 4219959; B: 1406653; A: 1406654; B: 1406655; A: 281331; B: 93777; A: 93778; B: 93779; A: 93780; B: 93781; A: 93782; B: 7214; A: 7215; B: 7216; A: 7217; B: 7218; A: 3609; B: 1203; A: 1204; B: 1205; A: 1206; B: 603; A: 201; B: 202; A: 203; B: 204; A: 205; B: 206; A: 207; B: 69; A: 70; B: 10; A: 11; B: 1 (wins)

Answer 2

Edit: I added code to compute the Nim values for the first $N$ positions of this game after the original post, as requested by @Timothy-Chow. Unfortunately my results don't match those given by @Peter-Taylor in the comments, so maybe I've not computed correctly.

Old: Here is the code for the calculations I alluded to in the comments, followed by the results when examining $n$ up to 10,000,000, of which 3,261,995 are winning numbers. As you can see, the gap $g$ occurs about $\frac{1}{2^{g-1}}$ of the time.

from sympy import primefactors
from collections import Counter
from functools import lru_cache

N = 10_000_000

@lru_cache(maxsize=N)
def iswinner(n):
    if n == 1:
        return True
    moves = [n // p for p in primefactors(n)] + [n+1]
    return all(not iswinner(move) for move in moves)

# yields the gaps in a sequence with more than 1 element
def gaps(seq):
    old = next(seq)
    for new in seq:
        yield new - old
        old = new

def winners():
    for n in range(1,N):
        if iswinner(n):
            yield n

freqs = Counter(gaps(winners()))

for gap in sorted(freqs.keys()):
    print(f'{gap:5}:{freqs[gap]:10}')


    2:   1570812
    3:    801091
    4:    446401
    5:    219317
    6:    111298
    7:     55754
    8:     29343
    9:     13833
   10:      7112
   11:      3482
   12:      1831
   13:       810
   14:       454
   15:       229
   16:       111
   17:        54
   18:        29
   19:        19
   20:         8
   21:         4
   22:         1
   23:         2

Edit 19 April 2023 (Nimbers): Even though we've been calling the numbers 1, 4, 6, 10, 14, ... winning numbers, they are actually losing positions for whichever player is facing them. So the so-called winning numbers have Nim value 0. (i.e. $\star 0$ for those versed in combinatorial game notation) The Nim value, also known as the Grundy value, is the minimum non-negative integer that is not equal to the Nim value of any of its reachable positions. This "minimum excluded" function was called mex by John Horton Conway.

The previously termed "winning numbers" have the value 0. These were computed using dynamic programming, a technique that usually only looks backwards in the array, but in this case, since $n+1$ is an allowable move from $n$, it has to look forward. The infinite game tree problem was avoiding by realizing that we'll eventually hit a prime, and a prime is a winning position (we divide by p and leave our opponent with the losing position 1). However, when computing non-zero positions as Nim values, we can't assume a player moves from a prime $p$ to 1, because it may be advantageous to not immediately move to *0 in a sum of games.

This algorithm works by finding the next zero position, and then backfilling the values to the previous zero position. For example, suppose we've computed the nimbers so far, and the we've just discovered 10 is a zero value position.

We can now compute the Nim value for 9, because the only moves are to 3 and to 10, and we know nimbers[3] is 1 and nimbers[10] is 0. Thus by the minimum-excluded principle the Nim value of 9 is 2. After that we can compute the values for 8 and 7.

The output of this program, which tallies all the Nim values, is

0: 3,261,996
1: 3,203,496
2: 2,030,151
3: 1,224,407
4:   258,511
5:    21,142
6:       297

Unfortunately, this does not match the values given in the comments, so it may be wrong. Please feel free to let me know!

from sympy import primefactors
from collections import Counter
from functools import lru_cache
from itertools import count

N = 10_000_000

@lru_cache(maxsize=N)
def iswinner(n):
    if n == 1:
        return True
    moves = [n // p for p in primefactors(n)] + [n+1]
    return all(not iswinner(move) for move in moves)

# return first non-negative integer not in l
def mex(l):
    for x in count():
        if x not in l:
            return x

extra = 30
nimbers = [None]*(N+extra)
nimbers[1] = 0
last = 1
n = 2

while last < N:
    if iswinner(n):
        nimbers[n] = 0
        k = n - 1
        while nimbers[k] is None:
            moves = [k // p for p in primefactors(k)] + [k+1]
            nimbers[k] = mex([nimbers[move] for move in moves])
            k -= 1
        last = n
    n += 1

freqs = Counter(nimbers[1:N+1])

for key in sorted(freqs.keys()):
    print(f'{key:5}:{freqs[key]:10,}')

Answer 3

The post is almost a year and a half old now, but I discovered it only recently and started working on it some months ago, since I found it a really interesting problem. Unfortunately I don't have definitive answers to any of the questions asked, however I wanted to share my observations, ideas, computations and conjectures, so maybe someone will be able to find out more starting from them. In order not to make this answer too long or messy, I won't mention everything I found and observed, only the main things, and I'll be brief with the proofs, but I do have a proof for all the things I say "it can be shown that".
Anyway I'm available to share more details about anything if asked or contacted!

I also hope my late answer can bring the discussion about this fascinating problem back to life and lead to new discoveries.

Introduction and basic observations

First, as it was already pointed out in another answer, the winning numbers are actually losing, since they're losing positions (P-positions) for the player who receives them and has to play next. That said, I'll name $L$ the set of such numbers.

Basic observations are that if $n$ is losing, then both $n-1$ and $n+1$ are winning, and so are all the numbers in the form $n \cdot p$ with $p$ prime. So I decided to study also this set $M$ of such numbers, numbers that I call $PM$ as in Prime Multiples (of Losing Numbers), since it is very closely related to the losing numbers and their distribution (I'll say more about it at the end). I also call the numbers not in that form $NPM$.

Now, $PM$ numbers are always winning, at least with one winning move, the move that divides by a prime, while instead $NPM$ numbers can be both winning and losing, but if they win, they can only win with the move $+1$, otherwise they'd be $PM$. This means in a set of consecutive $NPM$ numbers, winning and losing numbers alternate, and with this observation it's possible to prove that at least half of the $NPM$ numbers are losing.

---

Now, one thing to verify is that $L$ actually contains an infinite amount of numbers.

Proof. Suppose the number of losing numbers is instead finite, and let $N \geq 3$ (we know $4$ is losing so it exists) be the greatest of them. Also, let $p$ be a prime number $p < N$, whose existence is granted by Bertrand's Postulate, so that $p$ is such that $\lfloor\frac{N}{2}\rfloor < p \leq N-1$, and so $N+1 < 2p+1 \leq 2N-1$. Notice however that $2p$ is $NPM$ (it can't win by division), meaning either $2p$ is losing or $2p+1$ is, but they're both $>N$, which is a contradiction. □

Furthermore, we showed that if $N$ is losing the next losing number is $< 2N$ and that for each prime $p$ there exist at least one losing number, either $2p$ or $2p+1$. It's actually possible to do better than that: since semiprime numbers are all $NPM$, for the same above reasoning it's possible to show that if the density of $L$ goes to $0$ it does more slowly than the density of semiprime numbers, which is $\sim \frac{ln(lnN)}{lnN}$.

Since we showed there is an infinite amount of losing numbers, now it makes sense to talk about density, we'll assume they all converge, and denote $\rho_L$ and $\rho_M$ the density of losing and $PM$ numbers respectively.

One more little observation is that the amount of winning numbers that win with the move $+1$ is exactly the same as the amount of losing numbers (excluding $1$), and so the densities are the same.
This is simply because $n\,\,\textrm{loses}\iff n-1\,\,\textrm{wins with +1}$.

Results based on an independence assuption

One important result, is that if we assume the independence as $N\to\infty$ of the events $A:=$"$N + 1$ is winning" and $B:=$"$N/p$ is winning for any prime $p$ that divides $N$" we can easily derive the relations

$$\rho_M = \frac{1-2\rho_L}{1-\rho_L} \qquad \rho_L = \frac{1-\rho_M}{2-\rho_M}$$

coming from the fact that $\rho_L=\mathbb{P}(A\cap B)$ and $\rho_M=\mathbb{P}(\overline{B})$.

And I find this result important because it provides a relation between the two main sets we defined, and it is strongly supported by computational evidence!
Here is the plot up to $50$ millions of the values of $d_N(M)$ (density up to $N$) with the approximation we just derived. Below also a plot of the difference of the two, which is unclear whether it's going to $0$ or not, but up to what I've computed it's floating around $0.1\%$ error.

Under this same assumption, the density of losing numbers in the set of $NPM$ numbers is exactly $\frac{\rho_L}{1-\rho_M}=1-\rho_L$ and not just "at least a half" as said before. Another result that can be derived using this assumption is that $\rho_L\leq\frac{5-\sqrt{17}}{2}\approx0.438447$, but maybe this is not that interesting considering computations show decreasing values less than $\frac{1}{3}$.

Speculative conjecture about the exact value of the density

Now, despite the complete absence of evidence so far suggesting any value in particular as the limit of the density of losing numbers, I've stumbled upon the value $1-\frac{1}{\sqrt{2}}\approx0.292893$, which is the unique value of $\rho_L$ that maximases the product $\rho_L \cdot \rho_M$ (which under the same assumption is the probability that a number wins both by $+1$ and by division by a prime $p$), and so I'd conjecture it as the limit value of the density, as it would feel kind of "unbalanced" to see the pair $(\rho_L, \rho_L \cdot \rho_M)$ converge to any other point of the curve below.

I'm aware that it may be completely unrelated and I have nothing else about this value, but I still find it worth noticing and also not too unrealistic as a possible limit value.

Possibility of zero density and product set ideas

Another important aspect that was discussed in the comments under the original question was the possibility of the density $\rho_L$ converging to $0$. I've unsuccessfully tried many paths to prove or disprove this in the past months, but I have some ideas that maybe someone else can help me develop, so I'll add them to this answer.

First, following the argument that "the number of distinct prime factor increases as $N$ increases, so the probability that all moves lead to winning positions should decrease, and so the density might go to $0$" I found, using a lot of assumptions and approximations, the following approximation for the density of losing numbers:

$$d_N(L)\approx\frac{W\left(ln(lnN)+1\right)}{ln(lnN)+1}$$

where $W()$ is the Lambert W function.

And below is the graph of the two functions and a y-axis zoom.

But other than this, this approach didn't lead to many interesting things. It was still cool however to see the graphs and how extremely slowly the approximation goes to $0$.

---

Then, the most promising idea in my opinion, I thought about studying the properties of the product set $$A \cdot B = \{a \cdot b\,\,|\,\,a \in A, b \in B\}$$ since the set $M$ of $PM$ numbers is exactly the product set of $L$ and the set of primes. I tried showing that if a set has asymptotic density $0$ then the product with the primes has to have density $0$ as well (or at least $<1$), since this would prove that $\rho_L>0$ because we know $\rho_L=0\implies\rho_M=1$ (even without the independence assumption).
But I wasn't able to find a convincing (non-heuristic) proof, and there don't seem to be many articles online about the density of product sets, unfortunately. I found one that claimed to have found a set $A$ of density $0$ which multiplied by itself resulted in a set of density $1$, but nothing about primes.
The density of such sets is sadly very difficult to study because of possible overlaps, pairs $(a_1,b_1), (a_2,b_2)$ such that $a_1\cdot b_1 = a_2\cdot b_2$, resulting in a single element in the product set. But maybe someone else has some more experience than me with these sets and can develop this idea better, or find a valid proof of what I wrote above.

---

In short, my claim is that the density is highly unlikely to be zero, because the set $L$ would have to satisfy too many extremely specific and unlikely requirements: it would need to have not enough elements to have positive density, yet enough elements to result in a set of density $1$ when multiplied with the set of primes (if that is even possible), and even result in a set that doesn’t share any elements with the original.

What I tried to study in particular, without many useful results, was the sum

$$\sum_{k\,\in\,A\,\cap\,\{1,…,\frac{N}{2}\}} \pi\left(\frac{N}{k}\right)$$

which is an upper bound (because it also counts the overlaps) for the cardinality up to $N$ of the product set $A * P$ of a generic set $A$ and the set of primes. I tried with no luck to show that this sum if $A$ has density $0$ grows $<\!\!<\!N$, but I believe a deeper study of the behaviour of the overlaps is necessary to bound this cardinality better.

Computations

To conclude, I report some values I computed for the cardinalities and densities of the two main sets.

$N$	$|L\cap\{1,...,N\}|$	$d_N(L)$	$|M\cap\{1,...,N\}|$	$d_N(M)$
10,000	3,282	0.328200	5,084	0.508400
100,000	32,814	0.328140	51,141	0.511410
1,000,000	327,483	0.327483	513,140	0.513140
2,000,000	653,452	0.326726	1,028,300	0.514150
3,000,000	979,890	0.326630	1,543,261	0.514420
4,000,000	1,305,980	0.326495	2,058,613	0.514653
5,000,000	1,632,222	0.326444	2,574,266	0.514853
10,000,000	3,261,996	0.326200	5,153,468	0.515347
20,000,000	6,519,524	0.325976	10,318,317	0.515916
30,000,000	9,774,789	0.325826	15,486,156	0.516205
40,000,000	13,029,750	0.325744	20,654,498	0.516362
50,000,000	16,282,344	0.325647	25,825,777	0.516516