A083058 Number of eigenvalues equal to 1 of n X n matrix A(i,j)=1 if j=1 or i divides j.

1, 0, 1, 1, 2, 3, 4, 4, 5, 6, 7, 8, 9, 10, 11, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66

Offset: 1

Author

Michael Somos, Apr 18 2003

Keywords

• nonn

Comments

All numbers occur at least once, but terms > 1 of A000295 appear twice. - Robert G. Wilson v, Apr 19 2006

It appears that a(n) = Sum_{k=0..n-1} (1 + (-1)^A000108(k))/2 (n > 1). - Paul Barry, Mar 31 2008

Barry's observation above is true because A000108 obtains odd values only at points (2^j)-1 (A000225) and here the repeated values (A000295) occur precisely at positions given by A000225 and A000079. - Antti Karttunen, Aug 17 2013

a(n)+1 gives a lower bound for nonzero terms of A228086 and A228087. - Antti Karttunen, Aug 17 2013

Links

• Antti Karttunen, Table of n, a(n) for n = 1..8192
• J. B. Conrey, The Riemann Hypothesis, Notices Amer. Math. Soc., 50 (No. 3, March 2003), 341-353. See p. 347.
• Will Dana, Eigenvalues of the Redheffer Matrix and their relation to the Mertens function (2015), Theorem 5.
• Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions.
• Ralf Stephan, Table of generating functions.

Crossrefs

Cf. A002321, A070939, A143104.

Programs

Maple

A083058 := proc(n)
    if n = 1 then
        1;
    else
        n-floor(log[2](n))-1 ;
    end if;
end proc:
seq(A083058(n),n=1..40) ; # R. J. Mathar, Jul 23 2017

Mathematica

a[1] = 1; a[n_] := n - Floor[Log[2, n]] - 1;
Array[a, 100] (* Jean-François Alcover, Feb 27 2019 *)

PARI

a(n)=if(n<2,n>0,n-floor(log(n)/log(2))-1)

PARI

a(n)= if(n<1, 0, valuation( subst( charpoly( matrix(n, n, i, j, (j==1) || (0==j%i))), x, x+1), x))

Python

def a(n): return n - n.bit_length() + (n == 1)  # Matthew Andres Moreno, Jan 04 2024

Scheme

(define (A083058 n) (if (< n 2) n (- n (A070939 n)))) ;; Antti Karttunen, Aug 17 2013

Formula

a(n) = n - A070939(n), n > 1.

a(1)=1, else a(n)=b(n) with b(0)=0, b(2n)=b(n)+n-1, b(2n+1)=b(n)+n. - Ralf Stephan, Oct 11 2003

Except for a(1), a(n) = n - 1 - floor(log(2,n)). - Robert G. Wilson v, Apr 19 2006

It seems that a(n) = A182220(n+1)-1 for all n > 1. - Antti Karttunen, Aug 17 2013