A330358 -id:A330358 - cp's OEIS frontend

A110592 Number of digits in base-5 representation of n. String length of A007091.

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

Offset: 0

Jonathan Vos Post, Jul 29 2005

In terms of the repetition convolution operator #, where (sequence A) # (sequence B) = the sequence consisting of A(n) copies of B(n), then this sequence is the repetition convolution A110595 # 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.

G. C. Greubel, Table of n, a(n) for n = 0..5000

Cf. A007091, A081604, A110590, A110595, A330358.

Join[{1},IntegerLength[Range[110],5]] (* Harvey P. Dale, Aug 03 2016 *)

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

a(n) = floor(log_5(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)

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)

cp's OEIS Frontend

A110592 Number of digits in base-5 representation of n. String length of A007091.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

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

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