A071992 -id:A071992 - cp's OEIS frontend

A083038 A fractal sequence.

1, 1, 0, 0, 1, 1, 2, 4, 5, 5, 6, 6, 5, 5, 6, 6, 5, 5, 4, 2, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 2, 4, 5, 5, 6, 6, 5, 5, 6, 6, 7, 9, 10, 10, 11, 13, 14, 16, 19, 21, 22, 24, 25, 25, 26, 28, 29, 29, 30, 30, 29, 29, 30, 30, 31, 33, 34, 34, 35, 35, 34, 34, 35, 35, 34, 34, 33, 31, 30, 30, 29, 29, 30, 30

Offset: 1

Benoit Cloitre, Apr 17 2003

nonn

Sequence presents fractal patterns.

Boris Gourevitch, Graph of a(n).

Cf. A083035, A083036, A083037, A071992 (which presents similar fractal aspects).

a(n)=sum(k=1, n, A083037(k))

a(2*A001109(n)-1)=A001109(n) - Benoit Cloitre, Dec 12 2003

A005536 a(0) = 0; thereafter a(2n) = n - a(n) - a(n-1), a(2n+1) = n - 2a(n) + 1.

Original entry on oeis.org

0, 1, 0, 0, 1, 3, 3, 4, 3, 3, 1, 0, 0, 1, 0, 0, 1, 3, 3, 4, 6, 9, 10, 12, 12, 13, 12, 12, 13, 15, 15, 16, 15, 15, 13, 12, 12, 13, 12, 12, 10, 9, 6, 4, 3, 3, 1, 0, 0, 1, 0, 0, 1, 3, 3, 4, 3, 3, 1, 0, 0, 1, 0, 0, 1, 3, 3, 4, 6, 9, 10, 12, 12, 13, 12, 12, 13, 15, 15, 16, 18, 21, 22, 24, 27, 31, 33

Offset: 0

N. J. A. Sloane

A "Von Koch" sequence generated by the first Feigenbaum symbolic sequence.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. G. Stanton, W. L. Kocay and P. H. Dirksen, Computation of a combinatorial function, pp. 569-578 of C. J. Nash-Williams and J. Sheehan, editors, Proceedings of the Fifth British Combinatorial Conference 1975. Utilitas Math., Winnipeg, 1976.

T. D. Noe, Table of n, a(n) for n = 0..10000
J.-P. Allouche and J. Shallit, The Ring of k-regular Sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint 2016.
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 44 and 49.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Index entries for sequences related to binary expansion of n

Cf. A071992, A073059.

a[n_] := a[n] = If[n == 0, 0, hn = Floor[n/2]; If[OddQ[n], hn - 2 a[hn] + 1, hn - a[hn] - a[hn - 1]]]; t = Table[a[n], {n, 0, 100}] (* T. D. Noe, Mar 22 2012 *)

a(n)=-n*(n-2)+3*sum(k=1,n-1,sum(i=1,k,abs(subst(Pol(binary(i+1))- Pol(binary(i)),x,1)%2))) \\ Benoit Cloitre, May 29 2003

a(n)=polcoeff(1/(1-x)^2*sum(k=0,10, (-1)^k*x^2^k/(1+x^2^k)) +O(x^(n+1)),n)

from sympy.ntheory import digits
def A005536(n): return sum(sum((0,1,-1,0)[i] for i in digits(m,4)[1:]) for m in range(n+1)) # Chai Wah Wu, Jul 19 2024

Partial sums of A065359. a(n) = Sum_{i=0..n} Sum_{k=0..i} (-1)^k*(floor(i/2^k) - 2*floor(i/2^(k+1))). - Benoit Cloitre, Mar 28 2004
G.f.: (1/(1-x)^2) * Sum_{k>=0} (-1)^k*x^2^k/(1 + x^2^k). - Ralf Stephan, Apr 27 2003
a(n) = -n*(n-2) + 3*Sum_{k=1..n-1} Sum_{i=1..k} A035263(i+1), where A035263 is the first Feigenbaum symbolic sequence. - Benoit Cloitre, May 29 2003

More terms and better description from Ralf Stephan, Sep 13 2003

a(0)=0 added to data and offset changed by N. J. A. Sloane, Jun 16 2021 at the suggestion of Georg Fischer.

A073059 a(n) = (1/2)*(A073504(n+1) - A073504(n)).

Original entry on oeis.org

0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0

Offset: 1

Benoit Cloitre and Boris Gourevitch (boris(AT)pi314.net), Aug 16 2002

nonn

Let m be any fixed positive integer and let Fr(m,n) := 3*Sum_{k = 1..n} A073504(k) - n^2 + m*n. Then Fr(m,n) allows us to generate fractal sequences, i.e., there is an integer B(m) such that the graph for Fr(n,m) is fractal-like for 1 <= n <= B(m). B(m) depends on the parity of m: B(2*p+1) = (5/3)*(4^p - 1) and B(2*p) =(2/3)*(4^p - 1). [Formula for Fr(m,n) corrected by Petros Hadjicostas, Oct 21 2019]

Antti Karttunen, Table of n, a(n) for n = 1..16384
Benoit Cloitre, Graph of Fr(n,4) for 1 <= n <= B(4)
Benoit Cloitre, Graph of Fr(n,6) for 1 <= n <= B(6)
Benoit Cloitre, Graph of Fr(n,8) for 1 <= n <= B(8)
Benoit Cloitre, Graph of Fr(n,5) for 1 <= n <= B(5)
Benoit Cloitre, Graph of Fr(n,7) for 1 <= n <= B(7)
Benoit Cloitre, Graph of Fr(n,9) for 1 <= n <= B(9)
Index entries for characteristic functions

Not the same as the period-doubling sequence A096268!
Cf. A073504 and A071992 (curiously A071992 presents the same fractal aspects as Fr(n, m)).
Cf. A098725.

\\ To generate graphs:
for(n = 1,taille,u1=1; u2=n; while((u2!=u1)||((u2%2)==1),u3=u2; u2=floor(u2/2)+floor(u1/2); u1=u3; ); b[n]=u2; ) fr(m,k)=(3*sum(i=1,k,b[i]))-k^2+m*k; bound(m)=if((m%2)==1,p=(m-1)/2; 5/3*(4^p-1),2/3*(4^(m/2)-1)); m=5; fractal=vector(bound(m)); for(i=1,bound(m),fractal[i]=fr(m,i); ); Mm=vecmax(fractal) indices=vector(bound(m)); for(i=1,bound(m), indices[i]=i); myStr=plothrawexport("svg",indices,fractal,1);write("myPlot.svg",myStr);

A073059(n) = if(1==n,0,if(!(n%2),0,if(3==(n%4),1,A073059((n-1)/4)))); \\ Antti Karttunen, Oct 09 2018, after Ralf Stephan's Dec 11 2004 formula

up_to = 10000;
A073504list(up_to) = { my(v=vector(up_to)); for(n=1, up_to, u1=1; u2=n; while((u2!=u1)||((u2%2) == 1), u3=u2; u2=(u2\2)+(u1\2); u1=u3); v[n]=u2); (v); };
v073504 = A073504list(up_to);
A073504(n) = v073504[n];
A073059(n) = (1/2)*(A073504(n+1)-A073504(n)); \\ Antti Karttunen, Nov 27 2018, after code sent by Benoit Cloitre (personal communication), implementing the original definition

from functools import lru_cache
@lru_cache(maxsize=None)
def A073059(n): return (1 if n&2 else A073059(n>>2)) if n&1 else 0 # Chai Wah Wu, Feb 07 2025

a(4*k+3) = 1, a(4*k+2) = a(4*k+4) = 0, a(16*k+13) = 1, ...
A073504(n) = Sum_{k = 1..n} a(k) is asymptotic to 2*n/3.
a(2*n) = 0, a(4*n+3) = 1, a(4*n+1) = a(n). - Ralf Stephan, Dec 11 2004

Erroneous formula removed by Antti Karttunen, Oct 09 2018

A085009 "Von Koch" sequence generated by {1,1,2}.

Original entry on oeis.org

2, 0, 5, 8, 9, 8, 5, 0, 2, 2, 0, 5, 8, 9, 17, 23, 27, 29, 29, 27, 32, 35, 36, 35, 32, 27, 29, 29, 27, 23, 17, 9, 8, 5, 0, 2, 2, 0, 5, 8, 9, 8, 5, 0, 2, 2, 0, 5, 8, 9, 17, 23, 27, 29, 29, 27, 32, 35, 36, 44, 50, 54, 65, 74, 81, 86, 89, 90, 98, 104, 108, 110, 110, 108, 113, 116, 117, 116

Offset: 1

Benoit Cloitre, Jun 17 2003

nonn

The graph of the sequence is similar to, for example, A071992

Cf. A085006, A085007, A085009, A005536 ("Von Koch" sequence generated by {1, 2}).

a(n)= n+2 + sum(k=1, n, A085008(k))

A073504 A possible basis for finite fractal sequences: let u(1) = 1, u(2) = n, u(k) = floor(u(k-1)/2) + floor(u(k-2)/2); then a(n) = lim_{k->infinity} u(k).

Original entry on oeis.org

0, 0, 0, 2, 2, 2, 2, 4, 4, 4, 4, 6, 6, 8, 8, 10, 10, 10, 10, 12, 12, 12, 12, 14, 14, 14, 14, 16, 16, 18, 18, 20, 20, 20, 20, 22, 22, 22, 22, 24, 24, 24, 24, 26, 26, 28, 28, 30, 30, 30, 30, 32, 32, 34, 34, 36, 36, 36, 36, 38, 38, 40, 40, 42, 42, 42, 42, 44, 44, 44, 44, 46, 46, 46

Offset: 1

Benoit Cloitre and Boris Gourevitch (boris(AT)pi314.net), Aug 16 2002

nonn

The minimum number k(n) of iterations in order to have u(k(n)) = a(n) is asymptotic to log(n)/2. Let m be any fixed positive integer and let Fr(m,n) = 3*Sum_{k = 1..n} a(k) - n^2 + m*n; then Fr(m,n) is a fractal generator function, i.e., there is an integer B(m) such that the graph for Fr(n,m) presents same fractal aspects for 1 <= n <= B(m). B(m) depends on the parity of m. B(2*p+1) = (5/3)*(4^p-1); B(2*p) = (2/3)*(4^p-1). [Formula for Fr(m,n) corrected by Petros Hadjicostas, Oct 21 2019 using the PARI program below.]

Benoit Cloitre, Graph of Fr(n,4) for 1 <= n <= B(4).
Benoit Cloitre, Graph of Fr(n,6) for 1 <= n <= B(6).
Benoit Cloitre, Graph of Fr(n,8) for 1 <= n <= B(8).
Benoit Cloitre, Graph of Fr(n,5) for 1 <= n <= B(5).
Benoit Cloitre, Graph of Fr(n,7) for 1 <= n <= B(7).
Benoit Cloitre, Graph of Fr(n,9) for 1 <= n <= B(9).

Cf. A073059 and A071992 (curiously A071992 presents the same fractal aspects as Fr(n, m)).

for(n=1, taille, u1=1; u2=n; while((u2!=u1)||((u2%2) == 1), u3=u2; u2=floor(u2/2)+floor(u1/2); u1=u3; ); b[n]=u2; ) fr(m, k)=(3*sum(i=1, k, b[i]))-k^2+m*k; bound(m)=if((m%2) == 1, p=(m-1)/2; 5/3*(4^p-1), 2/3*(4^(m/2)-1)); m=5; fractal=vector(bound(m)); for(i=1, bound(m), fractal[i]=fr(m, i); ); Mm=vecmax(fractal) indices=vector(bound(m)); for(i=1, bound(m), indices[i]=i); myStr=plothrawexport("svg",indices,fractal,1);write("myPlot.svg",myStr); \\ To generate graphs

a(n) is asymptotic to 2*n/3.

cp's OEIS Frontend

A083038 A fractal sequence.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A005536 a(0) = 0; thereafter a(2n) = n - a(n) - a(n-1), a(2n+1) = n - 2a(n) + 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

Formula

Extensions

A073059 a(n) = (1/2)*(A073504(n+1) - A073504(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

PARI

PARI

Python

Formula

Extensions

A085009 "Von Koch" sequence generated by {1,1,2}.

Views

Author

Keywords

Comments

Crossrefs

Formula

A073504 A possible basis for finite fractal sequences: let u(1) = 1, u(2) = n, u(k) = floor(u(k-1)/2) + floor(u(k-2)/2); then a(n) = lim_{k->infinity} u(k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula