cp's OEIS Frontend

Apart from offset identical to A006501.

a(n) is the number of undirected rook moves on a n X n chessboard, considered up to rotations and reflections. - Hilko Koning, Aug 09 2025

Based on the fact that there are only O(sqrt(t)) distinct integers in the set S = {floor(t/1), floor(t/2), ..., floor(t/t)} and using combinatorics by fixing the number (a) as minimum, we can easily calculate this function in O(sigma(a=1->t^(1/3)) (log_2(floor(t/a)) + floor(t/a)^(1/2))).

The complexity can be reduced to O(sigma(a=1->t^(1/3)) (log_2(floor(t/a)) + floor(t/a)^(1/3))) = O(t^(5/9)).

There are many methods that take O(t^(5/9)) steps, but not all are effective; some of them have lower complexity but use too many division and multiplication steps. Some of them use precalculation and caching to speed things up, but are not as effective as the division-free algorithm that Richard Sladkey described.

It is known that for each (a), we only need a For loop of at most K = min((s-a)/2,sqrt(t/a)) iterations. If we can somehow calculate this in O(K^(1/2)) or even O(K^(1/3)) for each (a) then it is possible to calculate in O(t^(1/3)).

We can also calculate T(s, t) in O(t^(1/3)) if this function can be calculated fast enough: g(l, r, a, t) = Sum_{p = l..r} floor(t/(a*p)) for all a such that 1 <= a <= t^(1/3).

When s is small, we can try not fixing a as minimum and get O(s * t^(1/3)) complexity. You can also make the complexity not depend on O(f(t)) and get O(s^2) complexity and this can be further improved.

When s = t, the values on the main diagonal, T(s, s), are approximately 1.5*s^2 (tested with 10^7 numbers s <= 10^9 using a power regression algorithm).

The current best known algorithm O(t^(5/9)) (with modulo for large result) can run for s <= 10^18 and t <= 10^12 under 1 second and constant memory (820ms on GNU C++17 7.3.0 codeforces and 310ms on C++14 ideone).

As far as I know, the best complexity in theory is O(t^(2/3-c+o(1))) for small c > 0. Computing this table faster is as hard as the prime counting function and/or the divisor summatory function.

This sequence can be calculated by a recursive algorithm:

Let B1 be an array of finite length, the "1" denotes that it is the first generation. Let B1' be the reversed version of B1. Let C be the element-wise product C = B1 * B1'. Then B2 is a concatenation of taking each element of B1 and add all divisors of the corresponding element in C. If we start with B1 = {1} then we get this sequence of arrays: B2 = {2}, B3 = {3, 4, 6}, ... . a(n) is the length of the array Bn. In short the length of Bn+1 and so a(n+1) is the sum over A000005(Bn * Bn').

The transform used in the definition of this sequence is its own inverse, so if c = S(b) then b = S(c). The eigensequence is 2^n = S(2^n).

There exist some transformation pairs of infinite sequences in the database:

A000027 <--> A000142; A000079 <--> A000079; A000045 <--> A001654;

A026549 <--> A038754; A100071 <--> A001405; A058295 <--> A------;

A111286 <--> A098011; A093968 <--> A205825; A166447 <--> A------;

A098558 <--> A004277; A010551 <--> A087811; A100538 <--> A329227;

A079352 <--> A------; A082458 <--> A------; A008233 <--> A264635;

A138278 <--> A------; A006501 <--> A264557; A336496 <--> A------;

A019464 <--> A------; A062112 <--> A------; A171647 <--> A359039;

A279312 <--> A------; A031923 <--> A------.

These transformation pairs are conjectured:

A137326 <--> A------; A066332 <--> A300902; A208147 <--> A308546;

A057895 <--> A------; A349080 <--> A------; A019442 <--> A------;

A349079 <--> A------.

("A------" means not yet in the database.)

Some sequences in the lists above may need offset adjustment to force a beginning with 1,2,... in the transformation.

If we allowed signed rational numbers, further interesting transformation pairs could be observed. For example, 1/n will transform into factorials with alternating sign. 2^(-n) transforms into ones with alternating sign and 1/A000045(n) into A000045 with alternating sign.