A049804 -id:A049804 - cp's OEIS frontend

A110591 Number of digits in base-4 representation of n.

1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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

Offset: 0

Jonathan Vos Post, Jul 29 2005

Number of digits in A007090(n).

In terms of the repetition convolution operator #, where (sequence A) # (sequence B) = the sequence consisting of A(n) copies of B(n), this sequence is the repetition convolution A110594 # n. Over the set of positive infinite integer sequences, # gives a nonassociative noncommutative groupoid (magma) with a left identity (A000012) but no right identity, where the left identity is also a right nullifier and idempotent. For any positive integer constant c, the sequence c*A000012 = (c,c,c,c,...) is also a right nullifier; for c = 1, this is A000012; for c = 3 this is A010701.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000

Cf. A000012, A007090, A010701, A049804, A081604, A110594.

import Data.List (unfoldr)
a110591 0 = 1
a110591 n = length $
   unfoldr (\x -> if x == 0 then Nothing else Just (x, x `div` 4)) n
-- Reinhard Zumkeller, Apr 22 2011

A110592 := proc(n)
    if n = 0 then
        1;
    else
        1+floor(log[4](n)) ;
    end if;
end proc:
seq(A110592(n),n=0..50) ; # R. J. Mathar, Sep 02 2020

a[n_] := If[n == 0, 1, Floor[Log[4, n]] + 1];
a /@ Range[0, 100] (* Jean-François Alcover, Nov 24 2020 *)

G.f.: 1 + (1/(1 - x))*Sum_{k>=0} x^(4^k). - Ilya Gutkovskiy, Jan 08 2017

a(n) = floor(log_4(n)) + 1 for n >= 1. - Petros Hadjicostas, Dec 12 2019

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)

A049803 a(n) = n mod 3 + n mod 9 + ... + n mod 3^k, where 3^k <= n < 3^(k+1).

Original entry on oeis.org

0, 0, 0, 1, 2, 0, 1, 2, 0, 2, 4, 3, 5, 7, 6, 8, 10, 0, 2, 4, 3, 5, 7, 6, 8, 10, 0, 3, 6, 6, 9, 12, 12, 15, 18, 9, 12, 15, 15, 18, 21, 21, 24, 27, 18, 21, 24, 24, 27, 30, 30, 33, 36, 0, 3, 6, 6, 9, 12, 12, 15, 18, 9, 12, 15, 15, 18, 21, 21, 24, 27, 18

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 = 3 and a(n) = s(n,3).
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, A049804, A070939, A081604, A110591, A110592, A330358.

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

Table[n * Floor@Log[3, n] - Sum[Floor[n*3^-k]*3^k, {k, Log[3, n]}], {n, 100}] (* after Federico Provvedi in A049802*) (* Metin Sariyar, Dec 12 2019 *)

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

From Petros Hadjicostas, Dec 11 2019: (Start)
Conjecture: a(3*n+r) = 3*a(n) + r*A081604(n) = 3*a(n) + r*(floor(log_3(n)) + 1) for n >= 1 and r = 0, 1, 2.
If the conjecture above is true, the g.f. A(x) satisfies A(x) = 3*(1+x+x^2)*A(x^3) + x*(2*x+1)/(1-x^3) * Sum_{k >= 1} x^(3^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

A110591 Number of digits in base-4 representation of n.

Views

Author

Keywords

Comments

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

A049803 a(n) = n mod 3 + n mod 9 + ... + n mod 3^k, where 3^k <= n < 3^(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