A319875 - OEIS

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, 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

Table of n, a(n) for n=1..60.

Wikipedia, P-adic_order (also called p-adic valuation).

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

Cf. A000720, A006530.