|
| |
|
|
A319875
|
|
a(n) is the number of liberties of the group of n stones labeled 1 to n, by analogy to the game of go, in a pi(n)-dimensional board where a stone's coordinates are its label's p-adic valuations.
|
|
0
|
|
|
|
0, 1, 3, 4, 8, 9, 15, 18, 20, 21, 31, 34, 46, 48, 51, 56, 72, 77, 95, 100, 104, 107, 129, 136, 142, 145, 152, 157, 185, 192, 222, 232, 238, 242, 249, 258, 294, 298, 304, 313, 353, 362, 404, 413, 424, 429, 475, 488, 499, 511, 519, 528, 580, 594, 605, 617, 625, 631, 689, 703
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
COMMENTS
|
More formally, the board considered in the computation of a(n) is represented by N^pi(n), where N denotes the set of nonnegative integers and pi the prime-counting function (see A000720). For k an integer between 1 and n, stone k belongs to location (v_2(k), v_3(k), ..., v_{prime(pi(n))}(k)), where the v_p, for p = 2, 3, ..., prime(pi(n)) are the first pi(n) p-adic valuations (also called orders) of k. A liberty of a group of stones is an unoccupied location adjacent to a location occupied by a stone of the group. By definition, a(n) is the number of liberties of the group of stones k = 1 to n. Notice that the board only has one corner at (0, 0, ..., 0).
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(1) = 0.
a(p) = a(p-1) + p-1, for p a prime number.
a(c) = a(c-1) + pi(c) - pi(gpf(c)), for c a composite number, where gpf = A006530 denotes the "greatest prime factor of" function.
|
|
|
EXAMPLE
|
For n = 4, pi(n) = 2 gives a 2D-board in which the numbers from 1 to 4 are arranged as follows:
3-adic valuation
. ^ . . . . .
2 | x . . . .
1 | 3 x x . .
0 | 1 2 4 x .
+-----------> 2-adic valuation
0 1 2 3 .
There are 4 liberties (marked with an x), so a(4) = 4.
For n = 5, the fact that 5 is a prime adds a dimension to the board compared to when n was 4. So, the board being now 3D, stones 1 to 4 got one new liberty in the 5-adic valuation direction each. The removal of the liberty at (0,0,1) by stone number 5 is compensated by the creation of a new one at (0,0,2). Stone 5 creates no other liberties, as (1,0,1) and (0,1,1) were already taken into account earlier. The balance is the addition of 4 liberties, so a(5) = a(4) + 4 = 8.
For n = 6, the fact that 6 is composite leaves the dimension unchanged compared to when n was 5. The liberty removed by stone 6 at (1,1,0) is compensated by a created one at (1,2,0). The liberty adjacent to stone 6 at (2,1,0) was already taken into account as a liberty adjacent to stone 4. The liberty adjacent to stone 6 at (1,1,1) is a new liberty. The balance is the addition of 1 liberty, so a(6) = a(5) + 1 = 9.
|
|
|
MATHEMATICA
|
(* method 1 *)
a[n_] := Module[{E = Range[n],
P = Table[Prime[k], {k, 1, PrimePi[n]}], X, C},
X = DeleteDuplicates[Union[Flatten[Outer[Times, P, E]]]];
C = Complement[X, E]; Length[C]]
Table[a[n], {n, 1, 60}]
(* method 2 *)
a[n_] := a[n] = If[n == 1, 0, a[n - 1] + If[PrimeQ[n], n - 1, PrimePi[n] - PrimePi[FactorInteger[n][[-1, 1]]]]]
Table[a[n], {n, 1, 60}]
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
