A029827 -id:A029827 - cp's OEIS frontend

A036390 First differences of composite connected numbers (A029827).

30, 6, 4, 2, 6, 22, 10, 4, 12, 4, 2, 2, 4, 30, 18, 14, 2, 14, 4, 2, 2, 4, 2, 4, 2, 4, 6, 4, 2, 8, 2, 2, 4, 2, 68, 10, 2, 20, 10, 4, 18, 4, 2, 2, 10, 2, 4, 4, 2, 6, 2, 4, 8, 4, 4, 2, 4, 2, 2, 4, 10, 2, 2, 2, 2, 4, 2, 2, 4, 4, 2, 2, 4, 4, 2, 4, 92, 26, 10, 16, 2, 28, 10, 2, 6, 8, 20, 6, 8, 2, 8, 10, 6

Offset: 1

Labos Elemer

nonn

Observe the high local gaps, which arise between two connected numbers of binary order (A029837) g and g+1. E.g., five consecutive connected numbers in A029827 are 4087, 4089, 4095, 4369, and 4471, and corresponding differences are 2, 6, 274, and 102. Thus the density of connected numbers rises and falls in interval [ 2^(g-1), 2^g ].

Cf. A029827, A029837.

A036379 Special connected numbers: minimal and maximal connected numbers (cf. A029827) of a given binary order, i.e., between two consecutive powers of 2.

Original entry on oeis.org

15, 15, 45, 63, 85, 123, 153, 255, 323, 511, 603, 1023, 1139, 2047, 2227, 4095, 4369, 8189, 8777, 16383, 17219, 32767, 33667, 65535, 67591, 131069, 133897, 262143, 264967, 524285, 527621, 1048575, 1053443

Offset: 1

Labos Elemer

nonn

Observe in the sequence that although the values of 2^g-1 are often maximal marginal connected numbers, this is not an absolute rule.

			Between 1024 and 2048 (i.e., in the range with binary order 11) 1139 and 2047 are the smallest and largest composite connected numbers.

Cf. A029827.

A036381 Number of connected numbers (A029827) in the interval [2^(n-1)+1, 2^n].

Original entry on oeis.org

0, 0, 0, 1, 0, 5, 8, 21, 42, 89, 180, 361, 720, 1438, 2867, 5696, 11282, 22392, 44340, 87887, 174045, 344719, 682767, 1352375, 2678305, 5305631, 10510870, 20824910, 41264654, 81776998, 162083352, 321295873

Offset: 1

Labos Elemer

			From the 64 numbers with ceiling(log_2(x)) = 7, the following 8 are composite connected numbers: 85, 95, 99, 111, 115, 117, 119, 123. Among the others 13 primes, 4 true prime powers and 39 split numbers can be found.

Cf. A029827, A029837, A036378-A036390.

a(21)-a(32) from Sean A. Irvine, Oct 29 2020

A036387 Number of connected numbers (A029827) with binary order (A029837) <= n.

Original entry on oeis.org

0, 0, 0, 1, 1, 6, 14, 35, 77, 166, 346, 707, 1427, 2865, 5732, 11428, 22710, 45102, 89442, 177329, 351374, 696093, 1378860, 2731235, 5409540, 10715171, 21226041, 42050951, 83315605, 165092603, 327175955

Offset: 1

Labos Elemer

			Below 64 the following six composite connected numbers occur: 15,45,51,55,57,63, so a(6)=6.

Cf. A029827, A007053 and A029837, A036378-A036390.

a(21)-a(31) from Sean A. Irvine, Oct 29 2020

A029837 Binary order of n: log_2(n) rounded up to next integer.

Original entry on oeis.org

0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7

Offset: 1

N. J. A. Sloane

Or, ceiling(log_2(n)).
Worst-case cost of binary search.
Equal to number of binary digits in n unless n is a power of 2 when it is one less.
Thus a(n) gives the length of the binary representation of n - 1 (n >= 2), which is also A070939(n - 1).
Let x(0) = n > 1 and x(k + 1) = x(k) - floor(x(k)/2), then a(n) is the smallest integer such that x(a(n)) = 1. - Benoit Cloitre, Aug 29 2002
Also number of division steps when going from n to 1 by process of adding 1 if odd, or dividing by 2 if even. - Cino Hilliard, Mar 25 2003
Number of ways to write n as (x + 2^y), x >= 0. Number of ways to write n + 1 as 2^x + 3^y (cf. A004050). - Benoit Cloitre, Mar 29 2003
The minimum number of cuts for dividing an object into n (possibly unequal) pieces. - Karl Ove Hufthammer (karl(AT)huftis.org), Mar 29 2010
Partial sums of A209229; number of powers of 2 not greater than n. - Reinhard Zumkeller, Mar 07 2012

			a(1) = 0, since log_2(1) = 0.
a(2) = 1, since log_2(2) = 1.
a(3) = 2, since log_2(3) = 1.58...
a(n) = 7 for n = 65, 66, ..., 127, 128.
G.f. = x^2 + 2*x^3 + 2*x^4 + 3*x^5 + 3*x^6 + 3*x^7 + 3*x^8 + 4*x^9 + ... - _Michael Somos_, Jun 02 2019

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1989, p. 70.
G. J. E. Rawlins, Compared to What? An Introduction to the Analysis of Algorithms, W. H. Freeman, 1992; see pp. 108, 118.

T. D. Noe, Table of n, a(n) for n = 1..10000
Cino Hilliard, The x+1 conjecture [broken link]
Lionel Levine, Fractal sequences and restricted Nim, arXiv:math/0409408 [math.CO], 2004.
Eric Weisstein's World of Mathematics, Bit Length.
Index entries for sequences related to binary expansion of n

Cf. A000523, A070939, A000193, A000195, A004233, A113473, A053644.
Partial sums of A036987.
Used for several definitions: A029827, A036378-A036390. Partial sums: A001855.

a029837 n = a029837_list !! (n-1)
a029837_list = scanl1 (+) a209229_list
-- Reinhard Zumkeller, Mar 07 2012
(Common Lisp) (defun A029837 (n) (integer-length (1- n))) ; James Spahlinger, Oct 15 2012

[Ceiling(Log(2, n)): n in [1..100]]; // Vincenzo Librandi, Jun 14 2019

a:= n-> (p-> p+`if`(2^pAlois P. Heinz, Mar 18 2013

a[n_] := Ceiling[Log[2, n]]; Array[a, 105] (* Robert G. Wilson v, Dec 09 2005 *)
Table[IntegerLength[n - 1, 2], {n, 1, 105}] (* Peter Luschny, Dec 02 2017 *)
a[n_] := If[n < 1, 0, BitLength[n - 1]]; (* Michael Somos, Jul 10 2018 *)
Join[{0}, IntegerLength[Range[130], 2]] (* Vincenzo Librandi, Jun 14 2019 *)

{a(n) = if( n<1, 0, ceil(log(n) / log(2)))};

/* Set p = 1, then: */
xpcount(n,p) = for(x=1, n, p1 = x; ct=0; while(p1>1, if(p1%2==0,p1/=2; ct++,p1 = p1*p+1)); print1(ct, ", "))

{a(n) = if( n<2, 0, exponent(n-1)+1)}; /* Michael Somos, Jul 10 2018 */

def A029837(n):
    s = bin(n)[2:]
    return len(s) - (1 if s.count('1') == 1 else 0) # Chai Wah Wu, Jul 09 2020

def A029837(n): return (n-1).bit_length() # Chai Wah Wu, Jun 30 2022

(1 to 80).map(n => Math.ceil(Math.log(n)/Math.log(2)).toInt) // Alonso del Arte, Feb 19 2020

a(n) = ceiling(log_2(n)).
a(1) = 0; for n > 1, a(2n) = a(n) + 1, a(2n + 1) = a(n) + 1. Alternatively, a(1) = 0; for n > 1, a(n) = a(ceiling(n/2)) + 1. [corrected by Ilya Gutkovskiy, Mar 21 2020]
a(n) = k such that n^(1/k - 1) > 2 > n^(1/k), or the least value of k for which floor n^(1/k) = 1. a(n) = k for all n such that 2^(k - 1) < n < 2^k. - Amarnath Murthy, May 06 2001
G.f.: x/(1 - x) * Sum_{k >= 0} x^2^k. - Ralf Stephan, Apr 13 2002
A062383(n-1) = 2^a(n). - Johannes W. Meijer, Jul 06 2009
a(n+1) = -Sum_{k = 1..n} mu(2*k)*floor(n/k). - Benoit Cloitre, Oct 21 2009
a(n+1) = A113473(n). - Michael Somos, Jun 02 2019

Additional comments from Daniele Parisse

More terms from Michael Somos, Aug 02 2002

A036382 Odd split numbers: have a nontrivial factorization n=ab with a and b coprime, so that L(a) + L(b) <= L(n), where L(x) = A029837(x) = ceiling(log_2(x)).

Original entry on oeis.org

21, 33, 35, 39, 65, 69, 75, 77, 87, 91, 93, 105, 129, 133, 135, 141, 143, 145, 147, 155, 159, 161, 165, 175, 177, 183, 189, 195, 203, 217, 259, 261, 265, 267, 273, 275, 279, 285, 287, 291, 295, 297, 299, 301, 303, 305, 309, 315, 319, 321, 325, 327, 329, 339

Offset: 1

Labos Elemer

nonn

All even numbers are split numbers, except that prime powers -- here powers of 2 -- are by definition excluded.

The gaps g(n) = a(n+1) - a(n) are growing up to some local maximum before suddenly dropping down to a very small value and starting a new cycle of growth. The local maxima, distinctly seen as kinks in the graph, are g(1) = 12, g(4) = 26, g(12) = 24, g(30) = 42, g(70) = 48, g(157) = 110, g(348) = 96, g(748) = 160, g(1603) = 192, g(3379) = 446, g(7076) = 384, ... They occur at indices slightly larger than twice the preceding one; every other is of size 6*2^k, k = 1,2,3,... while those in between don't seem to follow a simple pattern and are sometimes larger than the subsequent gap of size 6*2^k. - M. F. Hasler, Apr 15 2017

			s = 39 is a split number since s = 39 = 3*13, gcd(3,13)=1 and L(3) + L(13) = 2 + 4 = L(39).

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A029827, A029837, A036378-A036390.

Select[Range[1, 340, 2], Function[n, Total@ Boole@ Map[And[Total@ Ceiling@ Log2@ # <= Ceiling@ Log2@ n, CoprimeQ @@ #] &, Map[{#, n/#} &, Rest@ Take[#, Ceiling[Length[#]/2]]]] > 0 &@ Divisors@ n]] (* Michael De Vlieger, Mar 03 2017 *)

Name corrected by Michael De Vlieger, Mar 03 2017

A036384 Number of odd split numbers (A036382) in the interval [2^(n-1), 2^n].

Original entry on oeis.org

0, 0, 0, 0, 1, 3, 8, 18, 40, 87, 191, 400, 855, 1776, 3697, 7644, 15752, 32365, 66304, 135570, 276590, 563432, 1146045, 2328063, 4724270, 9577176, 19397428, 39256129, 79390449, 160450210, 324088695, 654261484

Offset: 1

Labos Elemer

nonn

			Out of the 512 numbers with "binary order" ceiling(log_2(x)) = 10, there are 87 odd split numbers.

Cf. A029827, A029837, A036378-A036390.

Name simplified by M. F. Hasler, Apr 19 2017

a(21)-a(32) from Giovanni Resta, Apr 21 2017

A036385 Number of split numbers (A036382) with binary order (A029837) n, i.e., those in interval [ 2^(n-1), 2^n ].

Original entry on oeis.org

0, 0, 1, 3, 8, 18, 39, 81, 167, 342, 702, 1423, 2902, 5871, 11888, 24027, 48519, 97900, 197375, 397713, 800877, 1612007, 3243196, 6522366, 13112877, 26354391, 52951859, 106364992, 213608176, 428885665, 860959606

Offset: 1

Labos Elemer

			Out of the 128 numbers with the binary order 8, there are 81 split numbers (odd + even); so a(7)=81.

Cf. A029827, A029837, A036378-A036390.

a(20)-a(31) from Sean A. Irvine, Oct 29 2020

A036383 First differences of odd split numbers (A036382).

Original entry on oeis.org

12, 2, 4, 26, 4, 6, 2, 10, 4, 2, 12, 24, 4, 2, 6, 2, 2, 2, 8, 4, 2, 4, 10, 2, 6, 6, 6, 8, 14, 42, 2, 4, 2, 6, 2, 4, 6, 2, 4, 4, 2, 2, 2, 2, 2, 4, 6, 4, 2, 4, 2, 2, 10, 2, 4, 6, 6, 6, 8, 4, 2, 4, 4, 14, 4, 10, 14, 8, 30, 48, 2, 2, 2, 6, 2, 4, 2, 2, 2, 2, 4, 2, 4, 2, 2, 2, 4, 2, 4, 2, 6, 2, 4, 2, 2, 2, 4, 2

Offset: 1

Labos Elemer

nonn

The large local maxima are near powers of 2. Compare the differences of connected numbers (A036379).

Densities of connected (A029827) and split (A036382) numbers seem to behave in opposite way: where connected are dense, split ones are rare and vice versa.

			177, 183, 189, 195, 203, 217, 259, 261 are successive odd split numbers, so their sequence of first differences is 6, 6, 6, 8, 14, 42, 2.

Cf. A029837, A036378-A036390.

cp's OEIS Frontend

A036390 First differences of composite connected numbers (A029827).

Views

Author

Keywords

Comments

Crossrefs

A036379 Special connected numbers: minimal and maximal connected numbers (cf. A029827) of a given binary order, i.e., between two consecutive powers of 2.

Views

Author

Keywords

Comments

Examples

Crossrefs

A036381 Number of connected numbers (A029827) in the interval [2^(n-1)+1, 2^n].

Views

Author

Keywords

Examples

Crossrefs

Extensions

A036387 Number of connected numbers (A029827) with binary order (A029837) <= n.

Views

Author

Keywords

Examples

Crossrefs

Extensions

A029837 Binary order of n: log_2(n) rounded up to next integer.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Scala

Formula

Extensions

A036382 Odd split numbers: have a nontrivial factorization n=ab with a and b coprime, so that L(a) + L(b) <= L(n), where L(x) = A029837(x) = ceiling(log_2(x)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A036384 Number of odd split numbers (A036382) in the interval [2^(n-1), 2^n].

Views

Author

Keywords

Examples

Crossrefs

Extensions

A036385 Number of split numbers (A036382) with binary order (A029837) n, i.e., those in interval [ 2^(n-1), 2^n ].

Views

Author

Keywords

Examples

Crossrefs

Extensions

A036383 First differences of odd split numbers (A036382).

Views

Author

Keywords

Comments