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

%I #37 Oct 08 2021 03:44:35

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

%T 42,46,46,52,52,56,58,60,62,69,69,71,73,79,79,85,85,89,93,95,95,103,

%U 104,108,110,114,114,120,122,128,130,132,132,142

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

%C 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).

%C 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.

%H Alois P. Heinz, <a href="/A325459/b325459.txt">Table of n, a(n) for n = 0..10000</a>

%F From _M. F. Hasler_, Oct 11 2019: (Start)

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

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

%e The a(4) = 1 through a(10) = 8 partitions:

%e (22) (221) (33) (331) (44) (333) (55)

%e (222) (2221) (2222) (441) (3331)

%e (2211) (22111) (3311) (22221) (4411)

%e (22211) (33111) (22222)

%e (221111) (222111) (222211)

%e (2211111) (331111)

%e (2221111)

%e (22111111)

%p a:= proc(n) option remember; `if`(n<2, 0,

%p numtheory[tau](n)-2+a(n-1))

%p end:

%p seq(a(n), n=0..100); # _Alois P. Heinz_, Oct 11 2019

%t Table[Length[Select[IntegerPartitions[n],MatchQ[#,{x_,y__,1...}/;x>1&&SameQ[x,y]]&]],{n,0,30}]

%t (* Second program: *)

%t a[n_] := a[n] = If[n<2, 0, DivisorSigma[0, n] - 2 + a[n-1]];

%t a /@ Range[0, 100] (* _Jean-François Alcover_, May 20 2021, after _Alois P. Heinz_ *)

%o (Python)

%o from math import isqrt

%o 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

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

%Y Cf. A070824, A006218.

%K nonn

%O 0,7

%A _Gus Wiseman_, May 04 2019

%E Name changed at the suggestion of _Patrick James Smalley-Wall_ and _Luc Rousseau_ by _Gus Wiseman_, Oct 11 2019