cp's OEIS Frontend

In the game of Risk, an attack occurs when a player moves some number of armies into a territory defended by the armies of another player, and the outcome of the attack is determined by repeatedly rolling 6-sided dice according to the number of attacking and defending armies present, up to a maximum of 3 and 2 dice for the attacker and defender, respectively. Some number of armies are eliminated corresponding to comparing highest versus highest roll (with the loser losing one army), and second-highest versus second-highest roll (with the loser again losing one army), with ties going to the defending side. This continues either until the aggressor decides to retreat before the next roll, or until one side has lost all of its armies in the territory (in which case the victor has possession of the territory with the remaining armies).

Example: 3 of Alice's armies invade a territory held by 3 of Bob's armies; Alice rolls a (1,2,5) and Bob rolls a (4,2). Alice's 5 beats Bob's 4, and Bob's 2 beats Alice's 2 (as Bob is defending). Each side therefore loses one army, with each side having 2 armies remaining. Note that in this example, if Alice continues the attack, she will now roll only 2 dice against Bob's 2, thereby reducing her odds of eliminating Bob's armies in that territory. It can be shown that, in an arbitrarily large set of rolls, the odds favor the attacker. When the attacking player rolls 3 dice and the defending player rolls 2, of the 6^5 = 7776 possible rolls (all equally likely to occur), there are

2890 that result in the loss of 2 armies by the defender,

2275 that result in the loss of 2 armies by the attacker, and

2611 that result in the loss of 1 army by each.

However, in a 1-vs.-1 scenario, the defense is favored 7/12 to 5/12 because defenders win ties. Thus the probabilities are not so trivial as to which matchups are favorable. This is further complicated by intermediate-size armies which require repeated rolling, such as the 3-vs.-3 example above, where there is a nearly 2/3 chance that the attacker will lose troops that land them below the three-army threshold, but a 1/3 chance that the defender will be down to 1 defender against 3 attackers, which heavily favors the attacker. This requires recursively calculating the probabilities for the further downstream outcomes.

The triangle is formed by considering the probability of occurrence of a zero-indexed sum, s, of repeated rolls of an n-sided die. The probability is obtained by considering that the sum s = 0 appears with probability 1, and then for every s > 0, the sum s has a probability of appearing that is 1/n times the sum of the probability of appearing of each of the previous n values of s. The denominator of this probability is n^s, and the numerator is given in the rows of the triangle below.

For example, consider repeated rolls of an n=4-sided die. Looking at the corresponding portion of the sequence (i.e., 1, 1, 3, 5, 11), the probability that s = 0 occurs is 1/1, the probability that s = 1 occurs is 1/(n^s) = 1/4, the probability that s = 2 occurs is 5/(n^s) = 5/16, as there is a 1/4 chance that it is rolled from the start plus the 1/16 chance that it occurs when two consecutive 1's are rolled, and so on. Hence the probability for all s <= n numbers that can be rolled is (n+1)^(s-1)/n^s, with a global maximum at s = n.

However, for s > n, where there is no longer the chance that the sum occurs in a single roll, the fraction drops precipitously. It then resumes rising until s = floor((n+1)^(n+1)/n^n - n) (see A366451) which is the s having the maximum probability for s > n. Therefore this maximum will always occur at s <= 2n for all nontrivial dice (i.e., dice with n > 1 sides). Hence the rows of this triangle have been terminated at 2n since that guarantees the maximum, but a row could in principle be extended in perpetuity, wherein the fraction would stabilize about the value 2/(n+1).

A player chooses a target t > n and rolls a fair n-sided die repeatedly, keeping a running total of the numbers rolled. The player wins if t occurs in the sequence of running totals. a(n) is the choice of t that maximizes the probability of winning

A fair die with sides numbered 1 through n is assumed.

For given n, sum s occurs by adding one die role to a sum s-n .. s-1; so the probability p(s) of s occurring is p(s) = Sum_{i=1..n} p(s-i)*(1/n), i.e., the mean of the preceding n probabilities, and starting from p(0) = 1 for s=0 always occurring and p(s) = 0 for s < 0 never occurring.

It is immediately apparent upon plotting the probabilities from sum s = n+1 onwards that the highest probability is achieved at s = a(n).

It can be shown that, given the equation of n < s <= 2n, the maximum near a(n) is the only zero of the first derivative, and the second derivative is always negative, therefore any following probability must necessarily be less the maximum of the previous n probabilities, and therefore less than p(a(n)). Therefore any subsequent terms must then be less than p(a(n)). Because this is appending a rolling average of the previous n terms the probabilities dampen in their oscillations about a value of 2/(n+1).

Original definition: "Another test for divisibility by the n-th prime (see Comments for precise definition)."

Given a number M, delete its last digit d, then add d*a(n). If the result is divisible by prime(n), then M is also divisible by prime(n). This process may be repeated.

a(n) can be quickly calculated by finding the smallest multiple of prime(n) ending in 9, adding one, and dividing that result by 10. E.g., 7 -> 49 -> 5, 11 -> 99 -> 10, 13 -> 39 -> 4, 17 -> 119 -> 12, 19 -> 19 -> 2.

Equivalent definition: a(n) = 10^(p - 2) mod p, where p = prime(n). - Mauro Fiorentini, Feb 06 2025