login
a(n) = n minus the bottom entry of the difference table of the divisors of n.
1

%I #33 Mar 13 2020 16:58:42

%S 0,1,1,3,1,4,1,7,5,10,1,11,1,16,7,15,1,6,1,31,13,28,1,36,9,34,19,31,1,

%T -20,1,31,25,46,7,47,1,52,31,106,1,-62,1,31,21,64,1,151,13,66,43,31,1,

%U -34,19,8,49,82,1,727,1,88,71,63,25,-6,1,31,61,148,1,12,1,106,11,31,13,22,1,439,65,118,1,1541

%N a(n) = n minus the bottom entry of the difference table of the divisors of n.

%C From _David A. Corneth_, May 20 2016: (Start)

%C The bottom of the difference table of the divisors of n can be expressed in terms of the divisors of n and use of Pascal's triangle. Suppose a, b, c, d and e are the divisors of n. Then the difference table is as follows (rotated for ease of reading):

%C a

%C . . b-a

%C b . . . . c-2b+a

%C . . c-b . . . . . d-3c+3b-a

%C c . . . . d-2c+b . . . . . . e-4d+6c-4b+a

%C . . d-c . . . . . e-3d+3c-b

%C d . . . . e-2d+c

%C . . e-d

%C e

%C From here we can see Pascal's triangle occurring. Induction can be used to show that it's the case in general.

%C (End)

%H David A. Corneth, <a href="/A273133/b273133.txt">Table of n, a(n) for n = 1..10000</a>

%F a(n) = n - A187202(n).

%F a(n) = 1, if n is prime.

%F a(2^k) = 2^k - 1 = A000225(k), k >= 0.

%e For n = 18 the divisors of 18 are 1, 2, 3, 6, 9, 18, and the difference triangle of the divisors is:

%e 1 . 2 . 3 . 6 . 9 . 18

%e . 1 . 1 . 3 . 3 . 9

%e . . 0 . 2 . 0 . 6

%e . . . 2 .-2 . 6

%e . . . .-4 . 8

%e . . . . . 12

%e The bottom entry is 12, so a(18) = 18 - 12 = 6.

%t Array[# - First@ NestWhile[Differences, Divisors@ #, Length@ # > 1 &] &, 84] (* _Michael De Vlieger_, May 20 2016 *)

%o (Sage)

%o def A273133(n):

%o D = divisors(n)

%o T = matrix(ZZ, len(D))

%o for (m, d) in enumerate(D):

%o T[0, m] = d

%o for k in range(m-1, -1, -1) :

%o T[m-k, k] = T[m-k-1, k+1] - T[m-k-1, k]

%o return n - T[len(D)-1, 0]

%o print([A273133(n) for n in range(1, 85)]) # _Peter Luschny_, May 18 2016

%o (PARI) a(n) = my(d=divisors(n));n-sum(i=1,#d,binomial(#d-1,i-1)*(-1)^(#d-i)*d[i]) \\ _David A. Corneth_, May 20 2016

%Y Cf. A000005, A000040, A000225, A007318, A187202, A273102, A273103, A273109.

%K sign

%O 1,4

%A _Omar E. Pol_, May 17 2016