A020330 -id:A020330 - cp's OEIS frontend

A076877 a(n) = A020330(n) / n.

3, 5, 5, 9, 9, 9, 9, 17, 17, 17, 17, 17, 17, 17, 17, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 129, 129, 129, 129, 129, 129

Offset: 1

Reinhard Zumkeller, Nov 25 2002

nonn

			12 -> '1100' -> '1100'1100' = '11001100' -> 204 = A020330(12): a(12) = A020330(12)/12 = 204/12 = 17.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions, 2004.
Ralf Stephan, Table of generating functions.

Cf. A000523, A020330, A053644, A062383.

a[n_] := 1 + 2^Floor[Log2[n] + 1]; Array[a, 50] (* Amiram Eldar, Apr 07 2021 *)

a(n) = 1 + 2^(1 + Log2(n)), with Log2 = A000523.
a(n) = 1 + 2*A053644(n).
a(n) = 1 + A062383(n).

A233312 Terms of A114994 which are c-equivalent to "c-squares" (A020330).

Original entry on oeis.org

0, 3, 10, 15, 36, 43, 43, 63, 136, 147, 170, 175, 147, 175, 175, 255, 528, 547, 586, 591, 586, 683, 683, 703, 547, 591, 683, 703, 591, 703, 703, 1023, 2080, 2115, 2186, 2191, 2340, 2347, 2347, 2367, 2186, 2347, 2730, 2735, 2347, 2735, 2735, 2815, 2115, 2191

Offset: 0

Vladimir Shevelev, Dec 07 2013

About c-equivalent see in comment in A233249.

a(n) is even iff A171791(n+1) is odd - holds for at least the first 1028 terms. The reason, put very briefly, is that: a(n) is even if and only if n is the double of a "fibbinary number". Cf. A267508. [Jörgen Backelin, Jan 15 2016 added by Jeremy Gardiner, Jan 26 2016]

			c-square of 5 in binary is (10)(1)(10)(1)~(10)(10)(1)(1) which is 43 in decimal. So a(5)=43.

Peter J. C. Moses, Table of n, a(n) for n = 0..2499
Index entries for sequences related to binary expansion of n

Cf. A020330, A114994, A171791, A233249, A267508, A268032.

More terms from Peter J. C. Moses, Dec 07 2013

A290334 Numbers that are not the sum of three or fewer terms from A020330.

Original entry on oeis.org

1, 2, 4, 5, 7, 8, 11, 12, 14, 17, 19, 22, 24, 26, 27, 29, 31, 32, 34, 37, 38, 41, 43, 44, 47, 50, 52, 53, 59, 62, 68, 71, 77, 80, 85, 86, 89, 92, 94, 95, 97, 98, 101, 103, 104, 106, 107, 110, 112, 113, 115, 116, 119, 121, 122, 124, 125, 128, 130, 131, 133, 134, 137, 138, 140, 143, 145, 147, 148, 150, 152, 155, 157, 158, 160, 164, 165

Offset: 1

Jeffrey Shallit, Jul 27 2017

nonn

Not currently proved that there are infinitely many terms. It is conjectured that all integers > 686 are the sum of four binary squares.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Aayush Rajasekaran, Jeffrey Shallit and Tim Smith, Sums of Palindromes: an Approach via Nested-Word Automata, in: Rolf Niedermeier and Brigitte Vallée, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), Schloss Dagstuhl, 2018, pp. 54:1-54:12; arXiv preprint, arXiv:1706.10206 [cs.FL], June 30 2017.

Cf. A020330, A290335, A298731.

v = Table[n + n * 2^Floor[Log2[n] + 1], {n, 0, 12}]; Complement[Range[v[[-1]]], Plus @@@ Tuples[v, 3]] (* Amiram Eldar, Apr 09 2021 *)

A290335 Number of representations of n as a sum of four terms of A020330 (including 0), where order matters.

Original entry on oeis.org

1, 0, 0, 4, 0, 0, 6, 0, 0, 4, 4, 0, 1, 12, 0, 4, 12, 0, 12, 4, 6, 12, 0, 12, 4, 12, 6, 0, 24, 0, 10, 12, 0, 16, 0, 12, 10, 0, 12, 12, 13, 0, 12, 12, 0, 16, 12, 0, 16, 24, 6, 24, 12, 0, 32, 16, 12, 24, 24, 12, 25, 36, 0, 32, 36, 12, 40, 24, 12, 36, 36, 12, 34, 36, 12, 40, 36, 12, 30, 36, 12, 40, 36, 12, 52, 24, 12, 36, 24, 12, 34, 48, 6, 52, 36, 0, 54, 12, 12

Offset: 0

Jeffrey Shallit, Jul 27 2017

			For n = 24 there are four representations, which are the distinct permutations of [15,3,3,3].

Amiram Eldar, Table of n, a(n) for n = 0..10000
Parthasarathy Madhusudan, Dirk Nowotka, Aayush Rajasekaran and Jeffrey Shallit, Lagrange's Theorem for Binary Squares, in: I. Potapov, P. Spirakis and J. Worrell (eds.), 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), Schloss Dagstuhl, 2018, pp. 18:1-18:14; arXiv preprint, arXiv:1710.04247 [math.NT], 2017-2018.

Cf. A020330, A261132, A290334, A298731.

v = Table[k + k * 2^Floor[Log2[k] + 1], {k, 0, 8}]; a[n_] := If[(ip = IntegerPartitions[n, {4}, v]) == {}, 0, Plus @@ Length /@ (Permutations /@ ip)]; Table[a[n], {n, 0, v[[-1]]}] (* Amiram Eldar, Apr 09 2021 *)

A298731 Number of distinct representations of n as a sum of four terms of A020330 (including 0), where order does not matter.

Original entry on oeis.org

1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 2, 1, 0, 2, 0, 1, 2, 0, 1, 1, 2, 0, 1, 1, 0, 4, 1, 0, 2, 1, 1, 2, 1, 0, 3, 2, 1, 2, 1, 1, 3, 2, 0, 3, 2, 1, 4, 1, 1, 3, 2, 1, 3, 2, 1, 4, 2, 1, 3, 2, 1, 3, 2, 1, 4, 2, 1, 3, 1, 1, 4, 2, 1, 4, 2, 0, 4, 1, 1, 4, 2, 1, 3, 3, 0, 4, 1

Offset: 0

Jeffrey Shallit, Jan 25 2018

nonn

			For n = 45, the a(45) = 4 solutions are 45 = 15+15+15 = 36+3+3+3 = 15+10+10+10.

Amiram Eldar, Table of n, a(n) for n = 0..10000
Parthasarathy Madhusudan, Dirk Nowotka, Aayush Rajasekaran and Jeffrey Shallit, Lagrange's Theorem for Binary Squares, in: I. Potapov, P. Spirakis and J. Worrell (eds.), 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), Schloss Dagstuhl, 2018, pp. 18:1-18:14; arXiv preprint, arXiv:1710.04247 [math.NT], 2017-2018.

Cf. A020330, A290334, A290335 (which is the same sequence where order matters).

v = Table[k + k * 2^Floor[Log2[k] + 1], {k, 0, 8}]; a[n_] := Length @ IntegerPartitions[n, {4}, v]; Table[a[n], {n, 0, v[[-1]]}] (* Amiram Eldar, Apr 09 2021 *)

A233420 Minimal number of c-squares (A020330) and/or 1's which add to n.

Original entry on oeis.org

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

Offset: 1

Vladimir Shevelev, Dec 09 2013

nonn

Conjecture: the sequence is bounded by a constant.

			For n=33, we have 33=15+15+3. Since 33 is not in union of {1} and c-squares and is not a sum of two such numbers, then a(33)=3.

Cf. A020330, A233312.

v=vector(10^5,n,n+n<<#binary(n)); \\ choose large enough that v[#v] > n for a(n) below.
a(n)=if(setsearch(v,n),return(1));if(n<3,return(n));my(where=setsearch(v,n+1,1),t=n);if(!where,where=setsearch(v,n,1));forstep(i=where-1,1,-1,t=min(w(n-v[i]),t); if(t==1,return(2))); t+1 \\ Charles R Greathouse IV, Dec 10 2013

A308073 Lexicographically earliest sequence of positive terms such that for any distinct m and n, a(m) + dup(a(m+1)) <> a(n) + dup(a(n+1)) (where dup corresponds to A020330).

Original entry on oeis.org

1, 1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 2, 2, 3, 2, 4, 2, 5, 2, 6, 3, 4, 3, 5, 3, 6, 4, 4, 5, 4, 6, 5, 5, 6, 6, 7, 3, 7, 4, 7, 5, 7, 6, 8, 3, 8, 4, 8, 5, 8, 6, 9, 3, 9, 4, 9, 5, 9, 6, 10, 3, 10, 7, 7, 8, 7, 9, 7, 10, 8, 8, 9, 8, 10, 9, 9, 10, 10, 11, 3

Offset: 1

Rémy Sigrist, May 11 2019

			The first terms, alongside a(n) + dup(a(n+1)), are:
  n   a(n)  a(n)+dup(a(n+1))
  --  ----  ----------------
   1     1                 4
   2     1                11
   3     2                 5
   4     1                16
   5     3                 6
   6     1                37
   7     4                 7
   8     1                46
   9     5                 8
  10     1                55

Rémy Sigrist, Table of n, a(n) for n = 1..10000

See A308057 for other variants.

Cf. A020330.

s=0; v=1; for(n=1, 84, print1(v", "); for (w=1, oo, if (!bittest(s,x=v+w*(1+2^#binary(w))), s+=2^x; v=w; break)))

A343268 Numbers that are not the sum of exactly four terms from A020330 (not necessarily distinct).

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 25, 27, 28, 29, 30, 32, 34, 35, 37, 39, 41, 42, 44, 46, 47, 49, 51, 53, 56, 58, 62, 65, 67, 74, 83, 88, 95, 100, 104, 107, 109, 113, 116, 122, 125, 131, 134, 140, 143, 148, 149, 155

Offset: 1

Amiram Eldar, Apr 09 2021

nonn

Madhusudan et al. (2018) conjectured that a(112) = 1772 is the last term of this sequence.

Amiram Eldar, Table of n, a(n) for n = 1..112
Parthasarathy Madhusudan, Dirk Nowotka, Aayush Rajasekaran and Jeffrey Shallit, Lagrange's Theorem for Binary Squares, in: I. Potapov, P. Spirakis and J. Worrell (eds.), 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), Schloss Dagstuhl, 2018, pp. 18:1-18:14; arXiv preprint, arXiv:1710.04247 [math.NT], 2017-2018.

Cf. A020330, A290334, A290335, A298731, A343267.

v = Table[n + n * 2^Floor[Log2[n] + 1], {n, 1, 31}]; Complement[Range[0, 2000], Plus @@@ Tuples[v, 4]]

A344145 Positive numbers m such that A020330^k(m) belongs to A344022 for any k >= 0 (where f^k denotes the k-th iterate of f).

Original entry on oeis.org

2, 9, 10, 12, 35, 37, 38, 41, 42, 44, 49, 50, 52, 56, 139, 141, 142, 147, 149, 150, 153, 154, 156, 163, 165, 166, 169, 170, 172, 177, 178, 180, 184, 197, 198, 201, 202, 204, 209, 210, 212, 216, 226, 228, 232, 555, 557, 558, 563, 565, 566, 569, 570, 587, 589

Offset: 1

Rémy Sigrist, May 10 2021

The binary expansion of a term, say (b_1, ..., b_m), encodes an m-periodic nonintersecting infinite walk made of unit steps, with a +90-degree turn (resp. a -90-degree turn) at positions X=k' such that b_k = 1 (resp. b_k = 0) with k = k' mod m.

All positive terms of A002450 belong to this sequence.

			See illustration in Links section.

Rémy Sigrist, Illustration of initial terms

Cf. A002450, A020330, A344022.

is(n) = { my (b=if (n, binary(n), [0]), d=1, s=[d], z=2*d); b=concat([b,b,b,b]); for (k=1, #b, if (b[k], d*=I, d/=I); if (setsearch(s, z+=d), return (0), s=setunion(s, [z]); z+=d)); return (1) }

A293833 Number of primes p with A020330(n) < p < A020330(n+1).

Original entry on oeis.org

2, 2, 5, 3, 2, 2, 14, 4, 3, 3, 4, 1, 4, 3, 45, 3, 6, 6, 6, 5, 3, 6, 4, 5, 5, 6, 3, 5, 4, 6, 140, 12, 5, 9, 8, 11, 8, 5, 8, 8, 12, 8, 9, 7, 7, 8, 7, 6, 7, 9, 10, 5, 8, 11, 9, 8, 8, 7, 7, 9, 9, 7, 471, 14, 12, 15, 17, 15, 14, 13, 15, 14, 17, 12, 16, 16, 9, 17, 14, 12

Offset: 1

Zhi-Wei Sun, Oct 16 2017

nonn

Conjecture: a(n) > 0 for all n > 0, and a(n) = 1 only for n = 12.
The terms of A020330 are usually called "binary squares". Our conjecture is an analog of Legendre's conjecture that for each n = 1,2,3,... there is a prime between n^2 and (n+1)^2.
Those a(2^n-1) = pi(2*4^n+2^n) - pi(4^n) are relatively large, where pi(x) is the prime-counting function given by A000720.
We have verified that a(n) > 0 for all n = 1..2*10^7.

			a(1) = 2 since 5 and 7 are the only primes in the interval (A020330(1), A020330(2)) = (3, 10).
a(12) = 1 since 211 is the only prime greater than A020330(12) = 204 and smaller than A020330(13) = 221.
a(8191) = a(2^13 - 1) = pi(2^27 + 2^13) - pi(2^26) = 3646196.

Zhi-Wei Sun, Table of n, a(n) for n = 1..10000
Wikipedia, Legendre's conjecture

Cf. A000040, A000720, A014085, A020330.

f[n_]:=f[n]=(2^(Floor[Log[2,n]]+1)+1)*n;
a[n_]:=a[n]=PrimePi[f[n+1]-1]-PrimePi[f[n]];
Table[a[n],{n,1,80}]

cp's OEIS Frontend

A076877 a(n) = A020330(n) / n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A233312 Terms of A114994 which are c-equivalent to "c-squares" (A020330).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A290334 Numbers that are not the sum of three or fewer terms from A020330.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A290335 Number of representations of n as a sum of four terms of A020330 (including 0), where order matters.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A298731 Number of distinct representations of n as a sum of four terms of A020330 (including 0), where order does not matter.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A233420 Minimal number of c-squares (A020330) and/or 1's which add to n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A308073 Lexicographically earliest sequence of positive terms such that for any distinct m and n, a(m) + dup(a(m+1)) <> a(n) + dup(a(n+1)) (where dup corresponds to A020330).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A343268 Numbers that are not the sum of exactly four terms from A020330 (not necessarily distinct).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A344145 Positive numbers m such that A020330^k(m) belongs to A344022 for any k >= 0 (where f^k denotes the k-th iterate of f).

Views

Author

Keywords

Comments

Examples