|
%I #16 Jan 14 2019 02:58:01
%S 0,1,3,4,8,9,15,18,20,21,31,34,46,48,51,56,72,77,95,100,104,107,129,
%T 136,142,145,152,157,185,192,222,232,238,242,249,258,294,298,304,313,
%U 353,362,404,413,424,429,475,488,499,511,519,528,580,594,605,617,625,631,689,703
%N 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.
%C 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).
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/P-adic_order">P-adic_order</a> (also called p-adic valuation).
%F a(1) = 0.
%F a(p) = a(p-1) + p-1, for p a prime number.
%F 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.
%e For n = 4, pi(n) = 2 gives a 2D-board in which the numbers from 1 to 4 are arranged as follows:
%e 3-adic valuation
%e . ^ . . . . .
%e 2 | x . . . .
%e 1 | 3 x x . .
%e 0 | 1 2 4 x .
%e +-----------> 2-adic valuation
%e 0 1 2 3 .
%e There are 4 liberties (marked with an x), so a(4) = 4.
%e 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.
%e 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.
%t (* method 1 *)
%t a[n_] := Module[{E = Range[n],
%t P = Table[Prime[k], {k, 1, PrimePi[n]}], X, C},
%t X = DeleteDuplicates[Union[Flatten[Outer[Times, P, E]]]];
%t C = Complement[X, E]; Length[C]]
%t Table[a[n], {n, 1, 60}]
%t (* method 2 *)
%t a[n_] := a[n] = If[n == 1, 0, a[n - 1] + If[PrimeQ[n], n - 1, PrimePi[n] - PrimePi[FactorInteger[n][[-1, 1]]]]]
%t Table[a[n], {n, 1, 60}]
%Y Cf. A000720, A006530.
%K nonn
%O 1,3
%A _Luc Rousseau_, Sep 30 2018
|
