A123709 a(n) is the number of nonzero elements in row n of triangle A123706.

1, 2, 3, 4, 3, 4, 3, 4, 4, 6, 3, 8, 3, 6, 7, 4, 3, 8, 3, 8, 7, 6, 3, 8, 4, 6, 4, 8, 3, 11, 3, 4, 7, 6, 7, 8, 3, 6, 7, 8, 3, 11, 3, 8, 8, 6, 3, 8, 4, 8, 7, 8, 3, 8, 7, 8, 7, 6, 3, 16, 3, 6, 8, 4, 7, 12, 3, 8, 7, 14, 3, 8, 3, 6, 8, 8

Offset

1,2

Comments

Triangle A123706 is the matrix inverse of triangle A010766, where A010766(n,k) = [n/k]. a(n) = 4 when n is in A123710. a(n) = 8 when n is in A123711. a(n) = 16 when n is in A123712.

Links

M. F. Hasler, Table of n, a(n) for n = 1..500

Peter Luschny, Re: Is the A123706 triangle an extension of the Moebius function?, seqcomp list, Feb 12 2012

Formula

a(n) = 2^(m+1) - 1 when n is the product of m distinct odd primes. [Corrected by M. F. Hasler, Feb 13 2012]

For any k>1, a(n)=2^k if, and only if, n is a nonsquarefree number with A001221(n) = k-1 (= omega(n), number of distinct prime factors), with the only exception of a(n=6)=2^2. - M. F. Hasler, Feb 12 2012

A123709(n) = 1 + #{ k in 1..n-1 | Moebius(n,k+1) <> Moebius(n,k) }, where Moebius(n,k)={moebius(n/k) if n=0 (mod k), 0 else}, cf. link to message by P. Luschny. - M. F. Hasler, Feb 13 2012

Example

a(n) = 3 when n is an odd prime.
a(n) = 7 when n is the product of two different odd primes.  [Corrected by M. F. Hasler, Feb 13 2012]
a(n) = 15 when n is the product of three different odd primes.  [Corrected by M. F. Hasler, Feb 13 2012]

Mathematica

Moebius[i_, j_]:=If[Divisible[i, j], MoebiusMu[i/j], 0];
A123709[n_]:=Length[Select[Table[Moebius[n, j]-Moebius[n, j+1], {j, 1, n}], #!=0&]];
Array[A123709, 500] (* Enrique Pérez Herrero, Feb 13 2012 *)

Prog

(PARI) {a(n)=local(M=matrix(n, n, r, c, if(r>=c, floor(r/c)))^-1); sum(k=1, n, if(M[n, k]==0, 0, 1))}
(PARI) A123709(n)=#select((matrix(n, n, r, c, r\c)^-1)[n, ], x->x)  \\ M. F. Hasler, Feb 12 2012
(PARI) A123709(n)={ my(t=moebius(n)); sum(k=2, n, t+0 != t=if(n%k, 0, moebius(n\k)))+1}  /* the "t+0 != ..." is required because of a bug in PARI versions <= 2.4.2, maybe beyond, which seems to be fixed in v. 2.5.1 */ \\ M. F. Hasler, Feb 13 2012

Crossrefs

Cf. A123706, A123707, A123708, A123710, A123711, A123712; A010766.

Sequence in context: A349229 A158515 A285884 * A165482 A323242 A099034

Adjacent sequences: A123706 A123707 A123708 * A123710 A123711 A123712

Keyword

nonn

Author

Paul D. Hanna, Oct 09 2006

Status

approved