A325459 Sum of numbers of nontrivial divisors (greater than 1 and less than k) of k for k = 1..n.

0, 0, 0, 0, 1, 1, 3, 3, 5, 6, 8, 8, 12, 12, 14, 16, 19, 19, 23, 23, 27, 29, 31, 31, 37, 38, 40, 42, 46, 46, 52, 52, 56, 58, 60, 62, 69, 69, 71, 73, 79, 79, 85, 85, 89, 93, 95, 95, 103, 104, 108, 110, 114, 114, 120, 122, 128, 130, 132, 132, 142

Offset: 0

Author

Gus Wiseman, May 04 2019

Keywords

• nonn

Comments

Also the number of integer partitions of n that are not hooks but whose augmented differences are hooks (original name). The augmented differences aug(y) of an integer partition y of length k are given by aug(y)i = y_i - y{i + 1} + 1 if i < k and otherwise aug(y)_k = y_k. For example, aug(6,5,5,3,3,3) = (2,1,3,1,1,3).

This sequence counts integer partitions with any number of ones and one part > 1 which appears at least twice. The Heinz numbers of these partitions are given by A325359.

Examples

			The a(4) = 1 through a(10) = 8 partitions:
  (22)  (221)  (33)    (331)    (44)      (333)      (55)
               (222)   (2221)   (2222)    (441)      (3331)
               (2211)  (22111)  (3311)    (22221)    (4411)
                                (22211)   (33111)    (22222)
                                (221111)  (222111)   (222211)
                                          (2211111)  (331111)
                                                     (2221111)
                                                     (22111111)
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..10000

Crossrefs

Cf. A049988, A093641, A325349, A325351, A325355, A325356, A325357, A325358.

Cf. A070824, A006218.

Programs

Maple

a:= proc(n) option remember; `if`(n<2, 0,
      numtheory[tau](n)-2+a(n-1))
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, Oct 11 2019

Mathematica

Table[Length[Select[IntegerPartitions[n],MatchQ[#,{x_,y__,1...}/;x>1&&SameQ[x,y]]&]],{n,0,30}]
(* Second program: *)
a[n_] := a[n] = If[n<2, 0, DivisorSigma[0, n] - 2 + a[n-1]];
a /@ Range[0, 100] (* Jean-François Alcover, May 20 2021, after Alois P. Heinz *)

Python

from math import isqrt
def A325459(n): return 0 if n == 0 else (lambda m: 2*(sum(n//k for k in range(1, m+1))-n)+(1-m)*(1+m))(isqrt(n)) # Chai Wah Wu, Oct 07 2021

Formula

From M. F. Hasler, Oct 11 2019: (Start)

a(n) = A006218(n) - 2*n + 1, in terms of partial sums of number of divisors.

a(n) = Sum_{k=1..n} A070824(k): partial sums of A070824 = number of nontrivial divisors. (End)

Extensions

Name changed at the suggestion of Patrick James Smalley-Wall and Luc Rousseau by Gus Wiseman, Oct 11 2019