A049803 -id:A049803 - cp's OEIS frontend

A081604 Number of digits in ternary representation of n.

1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5

Offset: 0

Reinhard Zumkeller, Mar 23 2003

a(n) is the length of row n in table A054635. - Reinhard Zumkeller, Sep 05 2014

			a(8) = 2 because 8 = 22_3, having 2 digits.
a(9) = 3 because 9 = 100_3, having 3 digits.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Eric Weisstein's World of Mathematics, Ternary.

Cf. A003137, A007089, A030341, A049803, A054635, A062153, A070939, A080342.
Cf. A062756, A077267, A081603.
Cf. A134021, A134025, A134026, A246435.

a081604 n = if n < 3 then 1 else a081604 (div n 3) + 1
-- Reinhard Zumkeller, Sep 05 2014, Feb 21 2013

A081604 := proc(n)
    max(1,1+ilog[3](n)) ;
end proc: # R. J. Mathar, Jul 12 2016

Table[Length[IntegerDigits[n, 3]], {n, 0, 99}] (* Alonso del Arte, Dec 30 2012 *)
Join[{1},IntegerLength[Range[120],3]] (* Harvey P. Dale, Apr 07 2019 *)

a(n) = A062153(n) + 1 for n >= 1.
a(n) = A077267(n) + A062756(n) + A081603(n);
From Reinhard Zumkeller, Oct 19 2007: (Start)
0 <= A134021(n) - a(n) <= 1;
a(A134025(n)) = A134021(A134025(n));
a(A134026(n)) = A134021(A134026(n)) - 1. (End)
a(n+1) = -Sum_{k=1..n} mu(3*k)*floor(n/k). - Benoit Cloitre, Oct 21 2009
a(n) = floor(log_3(n)) + 1. - Can Atilgan and Murat Erşen Berberler, Dec 05 2012
a(n) = if n < 3 then 1 else a(floor(n/3)) + 1. - Reinhard Zumkeller, Sep 05 2014
G.f.: 1 + (1/(1 - x))*Sum_{k>=0} x^(3^k). - Ilya Gutkovskiy, Jan 08 2017

A049802 a(n) = n mod 2 + n mod 4 + ... + n mod 2^k, where 2^k <= n < 2^(k+1).

Original entry on oeis.org

0, 0, 1, 0, 2, 2, 4, 0, 3, 4, 7, 4, 7, 8, 11, 0, 4, 6, 10, 8, 12, 14, 18, 8, 12, 14, 18, 16, 20, 22, 26, 0, 5, 8, 13, 12, 17, 20, 25, 16, 21, 24, 29, 28, 33, 36, 41, 16, 21, 24, 29, 28, 33, 36, 41, 32, 37, 40, 45, 44, 49, 52, 57, 0, 6, 10, 16, 16

Offset: 1

Clark Kimberling

nonn

There is the following connection between this sequence and A080277: A080277(n) = n + n*floor(log_2(n)) - a(n). Since A080277(n) is the solution to a prototypical recurrence in the analysis of the algorithm Merge Sort, that is, T(0) := 0, T(n) := 2*T(floor(n/2)) + n, the sequence a(n) seems to be the major obstacle when trying to find a simple, sum-free solution to this recurrence. It seems hard to get rid of the sum. - Peter C. Heinig (algorithms(AT)gmx.de), Oct 21 2006

When n = 2^k with k > 0 then a(n+1) = k. For this reason, when n-1 is a Mersenne prime then n - 1 = M(p) = 2^p - 1 = 2^a(n+1) - 1 and p = a(n+1) is prime. - David Morales Marciel, Oct 23 2015

Metin Sariyar, Table of n, a(n) for n = 1..32000 (terms 1..1000 from Paolo P. Lava)
B. Dearden, J. Iiams, and J. Metzger, A Function Related to the Rumor Sequence Conjecture, J. Int. Seq. 14 (2011), #11.2.3, Example 7.

Cf. A049803, A049804, A070939, A080277, A330358.

f:= proc(n) option remember; local m;
    if n::even then 2*procname(n/2)
    else m:= (n-1)/2; 2*procname(m) + ilog2(m) + 1
    fi
end proc:
f(1):= 0:
map(f, [$1..1000]); # Robert Israel, Oct 23 2015

Table[n * Floor@Log[2,n] - Sum[Floor[n*2^-k]*2^k, {k, Log[2,n]}], {n, 100}] (* Federico Provvedi, Aug 17 2013 *)

a(n) = sum(k=1, logint(n, 2), n % 2^k); \\ Michel Marcus, Dec 12 2019

def a(n): return sum(n % 2**k for k in range(n.bit_length())) # David Radcliffe, May 14 2025

From Robert Israel, Oct 23 2015: (Start)
a(2*n) = 2*a(n).
a(2*n+1) = 2*a(n) + A070939(n) for n >= 1.
G.f. A(x) satisfies A(x) = 2*(1+x)*A(x^2) + (x/(1-x^2))*Sum_{i>=1} x^(2^i). (End)

A049804 a(n) = n mod 4 + n mod 16 + ... + n mod 4^k, where 4^k <= n < 4^(k+1).

Original entry on oeis.org

0, 0, 0, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 2, 4, 6, 4, 6, 8, 10, 8, 10, 12, 14, 12, 14, 16, 18, 0, 2, 4, 6, 4, 6, 8, 10, 8, 10, 12, 14, 12, 14, 16, 18, 0, 2, 4, 6, 4, 6, 8, 10, 8, 10, 12, 14, 12, 14, 16, 18, 0, 3, 6, 9, 8, 11, 14, 17, 16, 19, 22

Offset: 1

Clark Kimberling

nonn

From Petros Hadjicostas, Dec 11 2019: (Start)
Conjecture: For b >= 2, consider the function s(n,b) = Sum_{1 <= b^j <= n} (n mod b^j) from p. 8 in Dearden et al. (2011). Then s(b*n + r, b) = b*s(n,b) + r*N(n,b) for 0 <= r <= b-1, where N(n,b) = floor(log_b(n)) + 1 is the number of digits in the base-b representation of n. As initial conditions, we have s(n,b) = 0 for 1 <= n <= b. (This is a generalization of a result by Robert Israel in A049802.)
Here b = 4 and a(n) = s(n,4).
We have N(n,2) = A070939(n), N(n,3) = A081604(n), N(n,4) = A110591(n), and N(n,5) = A110592(n).
If A_b(x) = Sum_{n >= 1} s(n,b)*x^n is the g.f. of the sequence (s(n,b): n >= 1) and the above conjecture is correct, then it can be proved that A_b(x) = b * A_b(x^b) * (1-x^b)/(1-x) + x * ((b-1)*x^b - b*x^(b-1) + 1)/((1-x)^2 * (1-x^b)) * Sum_{k >= 1} x^(b^k). (End)

Metin Sariyar, Table of n, a(n) for n = 1..32000
B. Dearden, J. Iiams, and J. Metzger, A Function Related to the Rumor Sequence Conjecture, J. Int. Seq. 14 (2011), #11.2.3, Example 7.

Cf. A049802, A049803, A070939, A081604, A110591, A110592, A330358.

a:= n-> add(irem(n, 4^j), j=1..ilog[4](n)):
seq(a(n), n=1..105);  # Petros Hadjicostas, Dec 13 2019 (after Alois P. Heinz's program for A330358)

Table[n * Floor@Log[4, n] - Sum[Floor[n*4^-k]*4^k, {k, Log[4, n]}], {n, 100}] (* Metin Sariyar, Dec 12 2019 *)
a[n_] := Sum[Mod[n, 4^j], {j, 1, Length[IntegerDigits[n, 4]] - 1}];
Array[a, 105] (* Jean-François Alcover, Dec 31 2021 *)

a(n) = sum(k=1, logint(n, 4), n % 4^k); \\ Michel Marcus, Dec 12 2019

From Petros Hadjicostas, Dec 11 2019: (Start)
Conjecture: a(4*n+r) = 4*a(n) + r*A110591(n) = 4*a(n) + r*(floor(log_4(n)) + 1) for n >= 1 and r = 0, 1, 2, 3.
If the conjecture above is true, the g.f. A(x) satisfies A(x) = 4*(1 + x + x^2 + x^3)*A(x^4) + x*(1 + 2*x + 3*x^2)/(1 - x^4) * Sum_{k >= 1} x^(4^k). (End)

A330358 a(n) = n mod 5 + n mod 25 + ... + n mod 5^k, where 5^k <= n < 5^(k+1).

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 2, 4, 6, 8, 5, 7, 9, 11, 13, 10, 12, 14, 16, 18, 15, 17, 19, 21, 23, 20, 22, 24, 26, 28, 0, 2, 4, 6, 8, 5, 7, 9, 11, 13, 10, 12, 14, 16, 18, 15, 17, 19, 21, 23, 20, 22, 24, 26, 28, 0, 2, 4, 6, 8, 5, 7, 9, 11, 13, 10

Offset: 1

Petros Hadjicostas, Dec 12 2019

Conjecture: For b >= 2, consider the function s(n,b) = Sum_{1 <= b^j <= n} (n mod b^j) from p. 8 in Dearden et al. (2011). Then s(b*n + r, b) = b*s(n,b) + r*N(n,b) for 0 <= r <= b-1, where N(n,b) = floor(log_b(n)) + 1 is the number of digits in the base-b representation of n. As initial conditions, we have s(n,b) = 0 for 1 <= n <= b. (This is a generalization of a result by Robert Israel in A049802.)
Here b = 5 and a(n) = s(n,5).
We have N(n,2) = A070939(n), N(n,3) = A081604(n), N(n,4) = A110591(n), and N(n,5) = A110592(n).
If A_b(x) = Sum_{n >= 1} s(n,b)*x^n is the g.f. of the sequence (s(n,b): n >= 1) and the above conjecture is correct, then it can be proved that A_b(x) = b * A_b(x^b) * (1-x^b)/(1-x) + x * ((b-1)*x^b - b*x^(b-1) + 1)/((1-x)^2 * (1-x^b)) * Sum_{k >= 1} x^(b^k).

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A049802, A049803, A049804, A070939, A081604, A110591, A110592.

a:= n-> add(irem(n, 5^j), j=1..ilog[5](n)):
seq(a(n), n=1..105);  # Alois P. Heinz, Dec 13 2019

a[n_] := Sum[Mod[n, 5^j], {j, 1, Length[IntegerDigits[n, 5]] - 1}];
Array[a, 105] (* Jean-François Alcover, Dec 31 2021 *)

a(n) = sum(k=1, logint(n, 5), n % 5^k);
for(n=1, 100, print1(a(n), ", ")); \\ (after Michel Marcus's program in A049804)

Conjecture: a(5*n+r) = 5*a(n) + r*A110592(n) = 5*a(n) + r*(floor(log_5(n)) + 1) for n >= 1 and r = 0, 1, 2, 3, 4.

If the conjecture above is true, the g.f. A(x) satisfies A(x) = 5*(1 + x + x^2 + x^3 + x^4)*A(x^5) + x*(1 + 2*x + 3*x^2 + 4*x^3)/(1 - x^5) * Sum_{k >= 1} x^(5^k).

cp's OEIS Frontend

A081604 Number of digits in ternary representation of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

A049802 a(n) = n mod 2 + n mod 4 + ... + n mod 2^k, where 2^k <= n < 2^(k+1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A049804 a(n) = n mod 4 + n mod 16 + ... + n mod 4^k, where 4^k <= n < 4^(k+1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A330358 a(n) = n mod 5 + n mod 25 + ... + n mod 5^k, where 5^k <= n < 5^(k+1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula