A007059 -id:A007059 - cp's OEIS frontend

A067139 Irreducible elements in OR-numbral arithmetic.

1, 2, 3, 5, 9, 11, 13, 17, 19, 23, 25, 29, 33, 35, 37, 39, 41, 43, 49, 53, 57, 65, 67, 69, 71, 75, 77, 79, 81, 83, 87, 89, 93, 97, 101, 105, 107, 113, 117, 121, 129, 131, 133, 135, 137, 139, 141, 143, 145, 147, 149, 151, 157, 159, 161, 163, 167, 169, 171, 177, 179

Offset: 1

Jens Voß, Jan 02 2002

Numbers m such that there is no number d in the range 1 < d < m with d*k = m for any 1 < k < m, where * is defined in A066376.
See A048888 for the definition of OR-numbral arithmetic. Note that 2 is the only prime element in OR-numbral arithmetic; for all other nonunit irreducibles x there exist numbers a and b not divisible by x such that x is a divisor of a * b.
Numbers m such that A066376(m) = 1.
1 together with primes in lunar arithmetic base 2. - N. J. A. Sloane, Aug 14 2010

Reinhard Zumkeller, Table of n, a(n) for n = 1..500
D. Applegate, M. LeBrun and N. J. A. Sloane, Dismal Arithmetic, arXiv:1107.1130 [math.NT], 2011. [Note: we have now changed the name from "dismal arithmetic" to "lunar arithmetic" - the old name was too depressing]
D. Applegate, M. LeBrun, N. J. A. Sloane, Dismal Arithmetic, J. Int. Seq. 14 (2011) # 11.9.8.
A. Frosini and S. Rinaldi, On the Sequence A079500 and Its Combinatorial Interpretations, J. Integer Seq., Vol. 9 (2006), Article 06.3.1.
Index entries for sequences related to dismal (or lunar) arithmetic

Cf. A003986, A067138, A048888, A007059.

See A169912 for the number of elements that are n bits long - N. J. A. Sloane, Aug 31 2010. See A171000 for the binary expansions.

import Data.List (elemIndices)
a067139 n = a067139_list !! (n-1)
a067139_list = 1 : map (+ 1) (elemIndices 1 a066376_list)
-- Reinhard Zumkeller, Mar 01 2013

Edited by N. J. A. Sloane at the suggestion of Andrew S. Plewe and Joshua Zucker, Jun 12 2007

A067399 Number of divisors of n in OR-numbral arithmetic.

Original entry on oeis.org

1, 2, 2, 3, 2, 4, 3, 4, 2, 4, 2, 6, 2, 6, 5, 5, 2, 4, 2, 6, 3, 4, 2, 8, 2, 4, 4, 9, 2, 10, 8, 6, 2, 4, 2, 6, 2, 4, 2, 8, 2, 6, 2, 6, 4, 4, 4, 10, 2, 4, 4, 6, 2, 8, 4, 12, 2, 4, 4, 15, 4, 16, 14, 7, 2, 4, 2, 6, 2, 4, 2, 8, 3, 4, 2, 6, 2, 4, 2, 10, 2, 4, 2, 9, 5, 4, 2, 8, 2, 8, 4, 6, 2, 8, 6, 12, 2, 4, 4, 6

Offset: 1

Jens Voß, Jan 23 2002

nonn

See A048888 for the definition of OR-numbral arithmetic. The example shows that this sequence is not multiplicative.

In other words, number of lunar divisors of n in base 2.

			a(15)=5 since [15] has the 5 OR-numbral divisors [1], [3], [5], [7] and [15].
If written as a triangle with rows of lengths 1,2,4,8,16,...:
1,
2, 2,
3, 2, 4, 3,
4, 2, 4, 2, 6, 2, 6, 5,
5, 2, 4, 2, 6, 3, 4, 2, 8, 2, 4, 4, 9, 2, 10, 8,
6, 2, 4, 2, 6, 2, 4, 2, 8, 2, 6, 2, 6, 4, 4, 4, 10, 2, 4, 4, 6, 2, 8, 4, 12, 2, 4, 4, 15, 4, 16, 14,
...,
the last terms in each row give A079500(n). The penultimate terms in the rows give 2*A079500(n-1). - _N. J. A. Sloane_, Mar 05 2011

N. J. A. Sloane, Table of n, a(n) for n = 1..1024
D. Applegate, M. LeBrun and N. J. A. Sloane, Dismal Arithmetic [Note: we have now changed the name from "dismal arithmetic" to "lunar arithmetic" - the old name was too depressing]
D. Applegate, M. LeBrun, N. J. A. Sloane, Dismal Arithmetic, J. Int. Seq. 14 (2011) # 11.9.8.
A. Frosini and S. Rinaldi, On the Sequence A079500 and Its Combinatorial Interpretations, J. Integer Seq., Vol. 9 (2006), Article 06.3.1.
Index entries for sequences related to dismal (or lunar) arithmetic

A079500 is the subsequence a(2^k-1). - N. J. A. Sloane, Feb 23 2011
Cf. A003986, A007059, A048888, A067138, A067139, A067398, A067400, A067401.
See A188548 for the sum of the divisors.

A067398 Squares in OR-numbral arithmetic.

Original entry on oeis.org

0, 1, 4, 7, 16, 21, 28, 31, 64, 73, 84, 95, 112, 125, 124, 127, 256, 273, 292, 311, 336, 341, 380, 383, 448, 473, 500, 511, 496, 509, 508, 511, 1024, 1057, 1092, 1127, 1168, 1205, 1244, 1279, 1344, 1385, 1364, 1407, 1520, 1533, 1532, 1535, 1792, 1841, 1892

Offset: 0

Jens Voß, Jan 23 2002

nonn

See A048888 for the definition of OR-numbral arithmetic.
Or, squares in lunar arithmetic base 2, written in base 10. - N. J. A. Sloane, Oct 02 2010
This sequence is not multiplicative; for example a(15) = 127 != 7 * 21 = a(3) * a(5). It is totally OR-numbral multiplicative: a([n] * [m]) = [a(n)] * [a(m)] in OR-numbral arithmetic. - Franklin T. Adams-Watters, Oct 27 2006

			A067398(5) = 21 since [5] * [5] = [21] in OR-numbral arithmetic.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
D. Applegate, M. LeBrun and N. J. A. Sloane, Dismal Arithmetic [Note: we have now changed the name from "dismal arithmetic" to "lunar arithmetic" - the old name was too depressing]
D. Applegate, M. LeBrun, N. J. A. Sloane, Dismal Arithmetic, J. Int. Seq. 14 (2011) # 11.9.8.
A. Frosini and S. Rinaldi, On the Sequence A079500 and Its Combinatorial Interpretations, J. Integer Seq., Vol. 9 (2006), Article 06.3.1.
Index entries for sequences related to dismal (or lunar) arithmetic

Cf. A003986, A007059, A048888, A067138, A067139, A067399, A067400, A067401.

a067398 :: Integer -> Integer
a067398 0 = 0
a067398 n = orm n n where
   orm 1 v = v
   orm u v = orm (shiftR u 1) (shiftL v 1) .|. if odd u then v else 0
-- Reinhard Zumkeller, Mar 01 2013

A119706 Total length of longest runs of 1's in all bitstrings of length n.

Original entry on oeis.org

1, 4, 11, 27, 62, 138, 300, 643, 1363, 2866, 5988, 12448, 25770, 53168, 109381, 224481, 459742, 939872, 1918418, 3910398, 7961064, 16190194, 32893738, 66772387, 135437649, 274518868, 556061298, 1125679616, 2277559414, 4605810806, 9309804278, 18809961926

Offset: 1

Adam Kertesz, Jun 09 2006, Jun 13 2006

nonn

a(n) divided by 2^n is the expected value of the longest run of heads in n tosses of a fair coin.

a(n) is also the sum of the number of binary words with at least one run of consecutive 0's of length >= i for i>=1. In other words A000225 + A008466 + A050231 + A050232 + ... . - Geoffrey Critzer, Jan 12 2013

			a(3)=11 because for the 8(2^3) possible runs 0 is longest run of heads once, 1 four times, 2 two times and 3 once and 0*1+1*4+2*2+3*1 = 11.

A. M. Odlyzko, Asymptotic Enumeration Methods, pp. 136-137
R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, 1996, page 372.

Alois P. Heinz, Table of n, a(n) for n = 1..1000
Steven Finch, Cantor-solus and Cantor-multus distributions, arXiv:2003.09458 [math.CO], 2020.

Cf. A334833.

A038374 := proc(n) local nshft, thisr, resul; nshft := n ; resul :=0 ; thisr :=0 ; while nshft > 0 do if nshft mod 2 <> 0 then thisr := thisr+1 ; else resul := max(resul, thisr) ; thisr := 0 ; fi ; nshft := floor(nshft/2) ; od ; resul := max(resul, thisr) ; RETURN(resul) ; end : A119706 := proc(n) local count, c, rlen ; count := array(0..n) ; for c from 0 to n do count[c] := 0 ; od ; for c from 0 to 2^n-1 do rlen := A038374(c) ; count[rlen] := count[rlen]+1 ; od ; RETURN( sum('count[c]*c','c'=0..n) ); end: for n from 1 to 40 do print(n,A119706(n)) ; od : # R. J. Mathar, Jun 15 2006
# second Maple program:
b:= proc(n, m) option remember; `if`(n=0, 1,
      `if`(m=0, add(b(n-j, j), j=1..n),
      add(b(n-j, min(n-j, m)), j=1..min(n, m))))
    end:
a:= proc(n) option remember;
     `if`(n<2, n, 2*a(n-1) +b(n, 0))
    end:
seq(a(n), n=1..40);  # Alois P. Heinz, Dec 19 2014

nn=10;Drop[Apply[Plus,Table[CoefficientList[Series[1/(1-2x)-(1-x^n)/(1-2x+x^(n+1)),{x,0,nn}],x],{n,1,nn}]],1]  (* Geoffrey Critzer, Jan 12 2013 *)

a(n+1) = 2*a(n) + A007059(n+2)
a(n) > 2*a(n-1). a(n) = Sum_{i=1..(2^n)-1} A038374(i). - R. J. Mathar, Jun 15 2006
From Geoffrey Critzer, Jan 12 2013: (Start)
O.g.f.: Sum_{k>=1} 1/(1-2*x) - (1-x^k)/(1-2*x+x^(k+1)). - Corrected by Steven Finch, May 16 2020
a(n) = Sum_{k=1..n} A048004(n,k) * k.
(End)
Conjecture: a(n) = A102712(n+1)-2^n. - R. J. Mathar, Jun 05 2025

More terms from R. J. Mathar, Jun 15 2006

Name edited by Alois P. Heinz, Mar 18 2020

A368279 a(n) is the number of compositions of n where the first part is the largest part and the last part is not 1. Row sums of A368579.

Original entry on oeis.org

1, 0, 1, 1, 2, 3, 6, 10, 19, 34, 63, 116, 216, 402, 754, 1417, 2674, 5061, 9608, 18286, 34888, 66706, 127798, 245284, 471561, 907964, 1750695, 3379992, 6533458, 12643162, 24491796, 47490688, 92170704, 179040096, 348064190, 677174709, 1318429534, 2568691317

Offset: 0

Peter Luschny, Jan 04 2024

nonn

Considering more generally the family of generating functions (1 - x)^n * Sum_{j>=0} (x^j / (1 - Sum_{k=1..j} x^k)) one finds several sequences related to compositions as indicated in the cross-references.

The compositions considered here can also be understood as perfectly balanced, ordered trees. See the linked illustrations. - Peter Luschny, Feb 26 2024

			a(0) = card({[0]}) = 1.
a(1) = card({}) = 0.
a(2) = card({[2]}) = 1.
a(3) = card({[3]}) = 1.
a(4) = card({[2, 2], [4]}) = 2.
a(5) = card({[2, 1, 2], [3, 2], [5]}) = 3.
a(6) = card({[2, 2, 2], [2, 1, 1, 2], [3, 3], [3, 1, 2], [4, 2], [6]}) = 6.
a(7) = card({[2, 2, 1, 2], [2, 1, 2, 2], [2, 1, 1, 1, 2], [3, 2, 2], [3, 1, 3], [3, 1, 1, 2], [4, 3], [4, 1, 2], [5, 2], [7]}) = 10.
a(8) = card({[2, 2, 2, 2],  [2, 2, 1, 1, 2], [2, 1, 2, 1, 2], [2, 1, 1, 2, 2], [2, 1, 1, 1, 1, 2], [3, 3, 2], [3, 2, 3], [3, 2, 1, 2], [3, 1, 2, 2], [3, 1, 1, 3], [3, 1, 1, 1, 2], [4, 4], [4, 2, 2], [4, 1, 3], [4, 1, 1, 2], [5, 3], [5, 1, 2], [6, 2], [8]}) = 19.

Peter Luschny, A generator for the A368279 compositions.
Peter Luschny, Some perfectly balanced, ordered trees illustrating A368279.

Cf. A368579, A369492, A007059, A092921, A188541.

Cf. A369115 (n=-2), A186537 left shifted (n=-1), A079500 (n=0), this sequence (n=1), A369116 (n=2).

gf := (1 - x)*sum(x^j / (1 - sum(x^k, k = 1..j)), j = 0..42):
ser := series(gf, x, 40): seq(coeff(ser, x, n), n = 0..37);
# Peter Luschny, Jan 19 2024

from functools import cache
@cache
def F(k, n):
    return sum(F(k,n-j) for j in range(1,min(k,n))) if n>1 else n
def a(n): return sum(F(k+1, n+1-k) - F(k+1, n-k) for k in range(n+1))
print([a(n) for n in range(38)])

def C(n): return sum(Compositions(n, max_part=k, inner=[k]).cardinality()
                 for k in (0..n))
def a(n): return C(n) - C(n-1) if n > 1 else 1 - n
print([a(n) for n in (0..28)])

a(n) = Sum_{k=0..n} (F(k+1, n+1-k) - F(k+1, n-k)) where F(k, n) = Sum_{j=1..min(k, n)} F(k, n-j) if n > 1 and otherwise n. F(k, n) refers to the generalized Fibonacci number A092921.
a(n) = A007059(n+1) - A007059(n).
G.f.: (1 - x)*(Sum_{j>=0} (x^j / (1 - Sum_{k=1..j} x^k ))) = (1 - x) * GfA079500. - Peter Luschny, Jan 20 2024

A127525 Number of ordered rooted trees where each subtree from given node has the same number of nodes.

Original entry on oeis.org

1, 1, 2, 3, 5, 6, 12, 13, 24, 33, 60, 61, 142, 143, 289, 447, 699, 700, 1558, 1559, 3518, 5375, 8977, 8978, 17179, 20305, 40471, 54808, 98182, 98183, 242068, 242069, 477002, 695051, 1183654, 1510612, 2629806, 2629807, 5057173, 7928654, 12366025, 12366026

Offset: 1

Franklin T. Adams-Watters, Jan 17 2007

nonn

			The tree shown below left counts, because the left subtree has 3 nodes and so does the right subtree and a similar condition holds for the subtrees. The tree shown on the right is not counted, because the left subtree has 3 nodes, while the right subtree has 4.
O..........O...O...O
|..........|....\./.
O...O...O..O.....O..
.\...\./....\....|..
.O...O......O...O..
..\./........\./...
...O..........O....

Alois P. Heinz, Table of n, a(n) for n = 1..5590

Cf. A000108, A127524, A007059.

a:= proc(n) option remember; `if`(n<2, n, add(
      a((n-1)/d)^d, d=numtheory[divisors](n-1)))
    end:
seq(a(n), n=1..45);  # Alois P. Heinz, Sep 08 2018

a[1] = 1;
a[n_] := a[n] = Sum[a[(n-1)/d]^d, {d, Divisors[n-1]}];
Array[a, 45] (* Jean-François Alcover, Oct 28 2020 *)

a(1) = 1; a(n+1) = Sum_{d|n} a(n/d)^d.

L.g.f.: -log(Product_{n>=1} (1 - a(n)*x^n)^(1/n)) = Sum_{n>=1} a(n+1)*x^n/n. - Ilya Gutkovskiy, Apr 29 2019

A067400 Non-uniquely factorizable OR-numbrals, i.e., numbrals for which there exist more than one different factorizations into irreducible factors (modulo order).

Original entry on oeis.org

15, 30, 31, 60, 62, 63, 85, 95, 111, 120, 123, 124, 125, 126, 127, 170, 175, 190, 191, 207, 222, 223, 239, 240, 243, 245, 246, 247, 248, 250, 251, 252, 253, 254, 255, 340, 341, 350, 351, 367, 379, 380, 381, 382, 383, 399, 414, 415, 443, 444, 445, 446, 447

Offset: 1

Jens Voß, Jan 24 2002

nonn

See A048888 for the definition of OR-numbral arithmetic.

			15 is in A067400 since [15] = [3] * [5] = [3]^3 and [3] and [5] are irreducible.

Cf. A003986, A007059, A048888, A067138, A067139, A067398, A067399, A067401.

A067401 Minimal non-uniquely factorizable OR-numbrals, i.e., numbrals that are not uniquely factorizable but for which all proper divisors are.

Original entry on oeis.org

15, 85, 95, 111, 123, 125, 175, 191, 207, 223, 239, 243, 245, 247, 251, 253, 351, 367, 379, 381, 399, 415, 443, 445, 447, 463, 483, 487, 493, 499, 501, 507, 585, 603, 621, 631, 639, 685, 687, 701, 725, 729, 731, 735, 757, 763, 783, 799, 827, 831, 873, 877

Offset: 1

Jens Voß, Jan 24 2002

nonn

See A048888 for the definition of OR-numbral arithmetic.

			15 is in A067401 since [15] = [3] * [5] = [3]^3 all divisors of [15] are uniquely factorizable.

Cf. A003986, A007059, A048888, A067138, A067139, A067398, A067399, A067400.

A356263 Triangle read by rows. The reduced triangle of the partition triangle of irreducible permutations (A356262). T(n, k) for n >= 1 and 0 <= k < n.

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 0, 3, 9, 1, 0, 5, 41, 24, 1, 0, 8, 150, 247, 55, 1, 0, 14, 494, 1746, 1074, 118, 1, 0, 24, 1537, 10126, 13110, 4050, 245, 1, 0, 43, 4642, 52129, 122521, 79396, 14111, 500, 1, 0, 77, 13745, 248494, 967644, 1126049, 425471, 46833, 1011, 1

Offset: 1

Peter Luschny, Aug 01 2022

The triangle can be seen as Euler's triangle A008292 restricted to irreducible permutations.

See the comments in A356116 for the definition of the terms 'partition triangle' and 'reduced partition triangle'. The reduction procedure is formalized in the Sage program in A356116.

			[1] [1]
[2] [0,  1]
[3] [0,  2,     1]
[4] [0,  3,     9,      1]
[5] [0,  5,    41,     24,      1]
[6] [0,  8,   150,    247,     55,       1]
[7] [0, 14,   494,   1746,   1074,     118,     1]
[8] [0, 24,  1537,  10126,  13110,    4050,   245,      1]
[9] [0, 43,  4642,  52129, 122521,   79396, 14111,    500,    1]
[10][0, 77, 13745, 248494, 967644, 1126049, 425471, 46833, 1011, 1]
.
The 5 irreducible permutations counted with T(5, 2) are 23451, 51234, 31524, 34512, and 45123.

Peter Luschny, Permutations with Lehmer, a SageMath Jupyter Notebook.

Cf. A356262 (partition triangle), A007059 (column 2), A003319 (row sums), A356114 (subdiagonal).

Cf. A008292, A356116.

# Uses function 'reduce_partition_triangle' from A356116.
reduce_partition_triangle(A356262_row, 8)

A224960 Number of compositions [p(1), p(2), ..., p(k)] of n such that p(j) >= p(1) - 1.

Original entry on oeis.org

1, 1, 2, 4, 7, 14, 26, 52, 101, 200, 396, 787, 1564, 3117, 6214, 12398, 24749, 49427, 98740, 197303, 394323, 788201, 1575695, 3150265, 6298732, 12594595, 25184598, 50361842, 100711888, 201404839, 402779246, 805509560, 1610940381, 3221753990

Offset: 0

Joerg Arndt, Apr 21 2013

nonn

			The a(5) = 14 such compositions of 5 are
01:  [ 1 1 1 1 1 ]
02:  [ 1 1 1 2 ]
03:  [ 1 1 2 1 ]
04:  [ 1 1 3 ]
05:  [ 1 2 1 1 ]
06:  [ 1 2 2 ]
07:  [ 1 3 1 ]
08:  [ 1 4 ]
09:  [ 2 1 1 1 ]
10:  [ 2 1 2 ]
11:  [ 2 2 1 ]
12:  [ 2 3 ]
13:  [ 3 2 ]
14:  [ 5 ]
(the two forbidden compositions are [ 3 1 1 ] and [ 4 1 ]).

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Cf. A171682 (compositions such that p(j) >= p(1)).
Cf. A079501 (compositions such that p(j) > p(1)).
Cf. A048888 (compositions such that p(j) <= p(1) + 1).
Cf. A007059 (compositions such that p(j) < p(1)).
Cf. A079500 (compositions such that p(j) <= p(1)).

b:= proc(n, i) option remember; `if`(n=0, 1, add(b(n-j,
      `if`(i=0, max(1, j-1), i)), j=`if`(i=0, 1, i)..n))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..50);  # Alois P. Heinz, May 02 2013

b[n_, i_] := b[n, i] = If[n == 0, 1, Sum[b[n - j, If[i == 0, Max[1, j - 1], i]], {j, If[i == 0, 1, i], n}]];
a[n_] := b[n, 0];
a /@ Range[0, 50] (* Jean-François Alcover, Dec 20 2020, after Alois P. Heinz *)

a(n) ~ 3 * 2^(n-3). - Vaclav Kotesovec, May 01 2014

cp's OEIS Frontend

A067139 Irreducible elements in OR-numbral arithmetic.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Extensions

A067399 Number of divisors of n in OR-numbral arithmetic.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A067398 Squares in OR-numbral arithmetic.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

A119706 Total length of longest runs of 1's in all bitstrings of length n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A368279 a(n) is the number of compositions of n where the first part is the largest part and the last part is not 1. Row sums of A368579.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Python

SageMath

Formula

A127525 Number of ordered rooted trees where each subtree from given node has the same number of nodes.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A067400 Non-uniquely factorizable OR-numbrals, i.e., numbrals for which there exist more than one different factorizations into irreducible factors (modulo order).

Views

Author

Keywords

Comments

Examples

Crossrefs

A067401 Minimal non-uniquely factorizable OR-numbrals, i.e., numbrals that are not uniquely factorizable but for which all proper divisors are.

Views

Author

Keywords

Comments

Examples