A068156 -id:A068156 - cp's OEIS frontend

A295515 The Euclid tree, read across levels.

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

Offset: 1

Peter Luschny, Nov 25 2017

nonn

Set N(x) = 1 + floor(x) - frac(x) and let '"' denote the ditto operator, referring to the previously computed expression. Assume the first expression is '0'. Then [0, repeat(N("))] will generate the natural numbers 0, 1, 2, 3, ... and [0, repeat(1/N("))] will generate the rational numbers 0/1, 1/1, 1/2, 2/1, 1/3, 3/2, ... Every reduced nonnegative rational number r appears exactly once in this list as a relatively prime pair [n, d] = r = n/d. We list numerator and denominator one after the other in the sequence.
The apt name 'Euclid tree' is taken from the exposition of Malter, Schleicher and Don Zagier. It is sometimes called the Calkin-Wilf tree. The enumeration is based on Stern's diatomic series (which is a subsequence) and computed by a modification of Dijkstra's 'fusc' function.
The tree listed has root 0, the variant with root 1 is more widely used. Seen as sequences the difference between the two trees is trivial: it is enough to leave out the first two terms; but as trees they are markedly different (see the example section).

			The tree with root 0 starts:
                                      [0/1]
                  [1/1,                                    1/2]
        [2/1,                1/3,                3/2,                2/3]
   [3/1,      1/4,      4/3,      3/5,      5/2,      2/5,      5/3,      3/4]
[4/1, 1/5, 5/4, 4/7, 7/3, 3/8, 8/5, 5/7, 7/2, 2/7, 7/5, 5/8, 8/3, 3/7, 7/4, 4/5]
.
The tree with root 1 starts:
                                      [1/1]
                  [1/2,                                    2/1]
        [1/3,                3/2,                2/3,                3/1]
   [1/4,      4/3,      3/5,      5/2,      2/5,      5/3,      3/4,      4/1]
[1/5, 5/4, 4/7, 7/3, 3/8, 8/5, 5/7, 7/2, 2/7, 7/5, 5/8, 8/3, 3/7, 7/4, 4/5, 5/1]

M. Aigner and G. M. Ziegler, Proofs from The Book, Springer-Verlag, Berlin, 3rd ed., 2004.

Peter Luschny, Table of n, row(n) for n = 1..12
N. Calkin and H. S. Wilf, Recounting the rationals, Amer. Math. Monthly, 107 (No. 4, 2000), pp. 360-363.
Edsger Dijkstra, Selected Writings on Computing, Springer, 1982, p. 232. EWD 578: More about the function 'fusc'.
Peter Luschny, Rational Trees and Binary Partitions.
A. Malter, D. Schleicher, and D. Zagier, New looks at old number theory, Amer. Math. Monthly, 120(3), 2013, pp. 243-264.
Moritz A. Stern, Über eine zahlentheoretische Funktion, J. Reine Angew. Math., 55 (1858), 193-220.
Index entries for sequences related to enumerating the rationals
Index entries for sequences related to trees

Cf. A002487, A174981, A294446 (Stern-Brocot tree), A294442 (Kepler's tree), A295511 (Schinzel-Sierpiński tree), A295512 (encoded by semiprimes).

# First implementation: use it only if you are not afraid of infinite loops.
a := x -> 1/(1+floor(x)-frac(x)): 0; do a(%) od;
# Second implementation:
lusc := proc(m) local a, b, n; a := 0; b := 1; n := m; while n > 0 do
if n mod 2 = 1 then b := a + b else a := a + b fi; n := iquo(n, 2) od; a end:
R := n -> 3*2^(n-1)-1 .. 2^n: # The range of level n.
EuclidTree_rat := n -> [seq(lusc(k+1)/lusc(k), k=R(n), -1)]:
EuclidTree_num := n -> [seq(lusc(k+1), k=R(n), -1)]:
EuclidTree_den := n -> [seq(lusc(k), k=R(n), -1)]:
EuclidTree_pair := n -> ListTools:-Flatten([seq([lusc(k+1), lusc(k)], k=R(n), -1)]):
seq(print(EuclidTree_pair(n)), n=1..5);

def A295515(n):
    if n == 1: return 0
    M = [0, 1]
    for b in (n//2 - 1).bits():
        M[b] = M[0] + M[1]
    return M[1]
print([A295515(n) for n in (1..85)])

Some characteristics in comparison to the tree with root 1, seen as a table with T(n,k) for n >= 1 and 1 <= k <= 2^(n-1). Here Tr(n,k), Tp(n,k), Tq(n,k) denotes the fraction r, the numerator of r and the denominator of r in row n and column k respectively.
                       With root 0:             With root 1:
Root Tr(1,1)           0/1                      1/1
Tp(n,1)                0,1,2,3,...              1,1,1,1,...
Tp(n,2^(n-1))          0,1,2,3,...              1,2,3,4,...
Tq(n,1)                1,1,1,1,...              1,2,3,4,...
Tq(n,2^(n-1))          1,2,3,4,...              1,1,1,1,...
Sum_k Tp(n,k)          0,2,8,26,...  A024023    1,3,9,27,...  A000244
Sum_k Tq(n,k)          1,3,9,27,...  A000244    1,3,9,27,...  A000244
Sum_k 2Tr(n,k)         0,3,9,21,...  A068156    2,5,11,23,... A083329
Sum_k Tp(n,k)Tq(n,k)   0,3,17,81,... A052913-1  1,4,18,82,... A052913
----
a(n) = A002487(floor(n/2)). - Georg Fischer, Nov 29 2022

A099257 a(1)=1, a(n+1) = if a(n)=n then 2*n+1 else smallest number not occurring earlier.

Original entry on oeis.org

1, 3, 2, 4, 9, 5, 6, 7, 8, 10, 21, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 22, 45, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 46, 93, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71

Offset: 1

Reinhard Zumkeller, Oct 09 2004

nonn

Permutation of the natural numbers with inverse A099258;
a(A033484(n)) = A033484(n);
a(A033484(n) + 1) = 2*A033484(n) + 1 = A068156(n).

Index entries for sequences that are permutations of the natural numbers

a(n) = if n = 3*2^k - 2 then n else (if n = 3*2^k - 1 then 2*n + 1 else n - 1).

A232598 T(n,k) = Stirling2(n,k) * OrderedBell(k).

Original entry on oeis.org

1, 1, 3, 1, 9, 13, 1, 21, 78, 75, 1, 45, 325, 750, 541, 1, 93, 1170, 4875, 8115, 4683, 1, 189, 3913, 26250, 75740, 98343, 47293, 1, 381, 12558, 127575, 568050, 1245678, 1324204, 545835, 1, 765, 39325, 582750, 3760491, 12391218, 21849366, 19650060, 7087261

Offset: 1

Tilman Piesk, Nov 26 2013

T(n,k) is the number of preferential arrangements of the k-part partitions of the set {1...n}.
2*T(n,k) is the number of formulas in first order logic that have an n-place predicate and use k variables, but don't include a negator.
4*T(n,k) is the number of such formulas that may include an negator.
The entries T(n,n) are A000670(n), i.e. the ordered Bell numbers.

			Let the colon ":" be a separator between two levels. E.g. in {1,2}:{3} the set {1,2} is on the first level, the set {3} is on the second level.
Compare descriptions of A083355 and A233357.
a(3,1) = 1:
{1,2,3}
a(3,2) = 9:
{1,2}{3}
{1,3}{2}
{2,3}{1}
{1,2}:{3}   {3}:{1,2}
{1,3}:{2}   {2}:{1,3}
{2,3}:{1}   {1}:{2,3}
a(3,3) = 13:
{1}{2}{3}
{1}{2}:{3}   {3}:{1}{2}
{1}{3}:{2}   {2}:{1}{3}
{2}{3}:{1}   {1}:{2}{3}
{1}:{2}:{3}
{1}:{3}:{2}
{2}:{1}:{3}
{2}:{3}:{1}
{3}:{1}:{2}
{3}:{2}:{1}
Triangle begins:
     k = 1   2     3      4      5       6       7      8          sums
n
1        1                                                            1
2        1   3                                                        4
3        1   9    13                                                 23
4        1  21    78     75                                         175
5        1  45   325    750    541                                 1662
6        1  93  1170   4875   8115    4683                        18937
7        1 189  3913  26250  75740   98343   47293               251729
8        1 381 12558 127575 568050 1245678 1324204 545835       3824282

Tilman Piesk, First 100 rows, flattened
Tilman Piesk, Preferential arrangements of set partitions (Wikiversity)

A008277 (Stirling2), A000670 (ordered Bell), A068156 (column k=2), A083355 (row sums: number of preferential arrangements), A233357 (number of preferential arrangements by number of levels).

T(n,k) = A008277(n,k) * A000670(k).
T(n,n) = A000670(n).
T(n,2) = A068156(n-1).
From Peter Bala, Nov 27 2013: (Start)
E.g.f.: 1/( 2 - exp(x*(exp(t) - 1)) ) = 1 + x*t + (x + 3*x^2)*t^2/2! + (x + 9*x^2 + 13*x^3)*t^3/3! + ....
Recurrence equation (for entries not on main diagonal): (n - k)*T(n,k) = C(n,1)*T(n-1,k) - C(n,2)*T(n-2,k) + C(n,3)*T(n-3,k) - ... (End)

A330530 Lexicographically earliest sequence of distinct positive integers such that the product of two consecutive terms is always divisible by 4.

Original entry on oeis.org

1, 4, 2, 6, 8, 3, 12, 5, 16, 7, 20, 9, 24, 10, 14, 18, 22, 26, 28, 11, 32, 13, 36, 15, 40, 17, 44, 19, 48, 21, 52, 23, 56, 25, 60, 27, 64, 29, 68, 30, 34, 38, 42, 46, 50, 54, 58, 62, 66, 70, 72, 31, 76, 33, 80, 35, 84, 37, 88, 39, 92, 41, 96, 43, 100, 45, 104

Offset: 1

Rémy Sigrist, Dec 17 2019

For any k > 0, let f_k be the lexicographically earliest sequence of distinct positive integers such that the product of two consecutive terms is always divisible by k:
- in particular:
     f_1 = f_2 = A000027,
     f_3 = A006368,
     f_4 = a (this sequence),
     f_6 = A330531,
- f_k is a permutation of the natural numbers,
- f_k(1) = 1, f_k(2) = max(2, k),
- if k is prime, then f_k corresponds to the integers that are not multiple of k interspersed with the integers that are multiple of k.
Apparently:
- for m > 0, the m-th run of consecutive terms such that gcd(a(n), 4) = 2 has A153893(m+1) terms,
- for m > 1, the m-th run of consecutive terms such that gcd(a(n), 4) = 1 or 4 has A068156(m+1) terms.

			The first terms, alongside their product with the next term, are:
  n   a(n)  a(n)*a(n+1)
  --  ----  -----------
   1     1            4
   2     4            8
   3     2           12
   4     6           48
   5     8           24
   6     3           36
   7    12           60
   8     5           80
   9    16          112
  10     7          140

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Rémy Sigrist, Colored scatterplot of the first 10000 terms
Index entries for sequences that are permutations of the natural numbers

Cf. A006368, A068156, A153893, A330531 (f_6), A330576 (inverse).

s=0; v=1; for (n=1, 10 000, print (n " " v); s+=2^v; for (w=1, oo, if (!bittest(s,w) && (v*w)%4==0, v=w; break)))

A143088 Triangle T(n,m) = (2^(m+1) - 1) * (2^(n-m+1) - 1), read by rows, 0 <= m <= n.

Original entry on oeis.org

1, 3, 3, 7, 9, 7, 15, 21, 21, 15, 31, 45, 49, 45, 31, 63, 93, 105, 105, 93, 63, 127, 189, 217, 225, 217, 189, 127, 255, 381, 441, 465, 465, 441, 381, 255, 511, 765, 889, 945, 961, 945, 889, 765, 511, 1023, 1533, 1785, 1905, 1953, 1953, 1905, 1785, 1533, 1023, 2047

Offset: 0

Roger L. Bagula and Gary W. Adamson, Oct 16 2008

Row sums are A045618.

Considered as a square array A(m,n) = (2^m - 1)(2^n - 1), (m, n >= 1), read by rising antidiagonals, this gives the number of m X n matrices of rank 1 over the field F_2. For a different field F_q, that number would be A(m,n) = (q^m - 1)(q^n - 1)/(q - 1). It satisfies the recurrence relation A(m,n) = A(m,n-1)*q + A(m,1). - M. F. Hasler, Sep 12 2024

			1;
3, 3;
7, 9, 7;
15, 21, 21, 15;
31, 45, 49, 45, 31;
63, 93, 105, 105, 93, 63;
127, 189, 217, 225, 217, 189, 127;
255, 381, 441, 465, 465, 441, 381, 255;
511, 765, 889, 945, 961, 945, 889, 765, 511;
1023, 1533, 1785, 1905, 1953, 1953, 1905, 1785, 1533, 1023;
2047, 3069, 3577, 3825, 3937, 3969, 3937, 3825, 3577, 3069, 2047;
...
From _M. F. Hasler_, Sep 12 2024: (Start)
Considered as a square array A(m,n), read by antidiagonals, with m, n >= 1, this represents the following matrix A:
    m \ n: 1  |  2  |  3  |  4  |  5  | ...
  -----+------+-----+-----+-----+-----+-----
    1  |   1  |  3  |   7 |  15 |  31 | ...
    2  |   3  |  9  |  21 |  45 |  93 | ...
    3  |   7  | 21  |  49 | 105 | 217 | ...
    4  |  15  | 45  | 105 | 225 | 465 | ...
   ...
Here each row equals twice the previous row plus the first row, and likewise for columns. See my comment relating this to rank 1 matrices over F_2. (End)

Cf. A000225 (first column), A068156 (second column).

Table[Table[(2^(m + 1) - 1)*(2^(n - m + 1) - 1), {m, 0, n}], {n, 0, 10}]; Flatten[%]

T(n,m) = (2^(m+1) - 1) * (2^(n-m+1) - 1) \\ M. F. Hasler, Sep 12 2024

T(n,m) = T(n,n-m).

T(n,0) = T(n,n) = 2^(n+1) - 1. - M. F. Hasler, Sep 12 2024

A146884 a(n) = 7*Sum_{k=0..n} 6^k.

Original entry on oeis.org

7, 49, 301, 1813, 10885, 65317, 391909, 2351461, 14108773, 84652645, 507915877, 3047495269, 18284971621, 109709829733, 658258978405, 3949553870437, 23697323222629, 142183939335781, 853103636014693, 5118621816088165

Offset: 0

Roger L. Bagula, Nov 02 2008

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (7,-6).

Cf. A003464, A005843, A068156, A100774, A132583, A146882, A146883, A146885.

[n le 2 select 7^n else 7*Self(n-1) -6*Self(n-2): n in [1..31]]; // G. C. Greubel, Oct 12 2022

a[n_]:= Sum[7*6^m, {m,0,n}]; Table[a[n], {n,0,30}]
Accumulate[7*6^Range[0,20]] (* Harvey P. Dale, Dec 18 2021 *)

[(7/5)*(6^(n+1)-1) for n in range(41)] # G. C. Greubel, Oct 12 2022

From G. C. Greubel, Oct 12 2022: (Start)
a(n) = (7/5)*(6^(n+1) - 1).
a(n) = 7*A003464(n+1).
a(n) = 7*a(n-1) - 6*a(n-2).
G.f.: 7/((1-x)*(1-6*x)).
E.g.f.: (7/5)*(6*exp(6*x) - exp(x)). (End)

A146885 a(n) = 8*Sum_{k=0..n} 7^k.

Original entry on oeis.org

8, 64, 456, 3200, 22408, 156864, 1098056, 7686400, 53804808, 376633664, 2636435656, 18455049600, 129185347208, 904297430464, 6330082013256, 44310574092800, 310174018649608, 2171218130547264, 15198526913830856

Offset: 0

Roger L. Bagula, Nov 02 2008

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (8,-7).

Cf. A005843, A023000, A068156, A100774, A132583, A146882, A146883, A146885.

[n le 2 select 8^n else 8*Self(n-1) -7*Self(n-2): n in [1..41]]; // G. C. Greubel, Oct 12 2022

a[n_]:= Sum[8*7^m, {m,0,n}]; Table[a[n], {n,0,30}]
LinearRecurrence[{8,-7}, {8,64}, 41] (* G. C. Greubel, Oct 12 2022 *)

[(4/3)*(7^(n+1)-1) for n in range(41)] # G. C. Greubel, Oct 12 2022

From G. C. Greubel, Oct 12 2022: (Start)
a(n) = (4/3)*(7^(n+1) - 1).
a(n) = 8*A023000(n+1).
a(n) = 8*a(n-1) - 7*a(n-2).
G.f.: 8/((1-x)*(1-7*x)).
E.g.f.: (4/3)*(7*exp(7*x) - exp(x)). (End)

A147758 Numbers whose binary representation is a palindrome formed from the reflected decimal expansion of the concatenation of 1, 0 and infinite digits 1.

Original entry on oeis.org

1, 3, 5, 9, 21, 45, 93, 189, 381, 765, 1533, 3069, 6141, 12285, 24573, 49149, 98301, 196605, 393213, 786429, 1572861, 3145725, 6291453, 12582909, 25165821, 50331645, 100663293, 201326589, 402653181, 805306365, 1610612733, 3221225469

Offset: 1

Omar E. Pol, Nov 11 2008

a(n) is the number whose binary representation is A147757(n).

Cf. A068156, A147757.

More terms from Sean A. Irvine, Nov 26 2009

A175160 Primes p such that 2p+3, 4p+9, 8p+21, 16p+45, 32p+93 and 64p+189 are also prime.

Original entry on oeis.org

6047, 477727, 507757, 955457, 1015517, 1360367, 1766357, 2224517, 2859977, 9628837, 13462777, 14757047, 16287247, 16878397, 18246997, 21026657, 22482767, 22892197, 23389517, 30596497, 31932227, 33145687, 35764397, 36180527, 36909277, 42627197, 43139027

Offset: 1

Vincenzo Librandi, Mar 08 2010

The coefficients of p in the definition are powers of 2; the constants in the definition are terms of A068156. - Harvey P. Dale, Mar 31 2012

			For p=6047, (12097, 24197, 48397, 96797, 193597, 387197) are prime.

Zak Seidov, Table of n, a(n) for n = 1..12628 (all terms up to 3*10^11)

[ p: p in PrimesUpTo(50000000) | IsPrime(p) and IsPrime(2*p+3) and IsPrime(4*p+9) and IsPrime(8*p+21) and IsPrime(16*p+45) and IsPrime(32*p+93) and IsPrime(64*p+189)];

okQ[n_]:=And@@PrimeQ[{3+2*n,9+4*n,21+8*n,45+16*n,93+32*n,189+64*n}]; Select[Prime[Range[2220000]],okQ] (* Harvey P. Dale, Mar 31 2012 *)

A247231 Triangular array read by rows: T(n,k) is the number of ways to partition an n-set into exactly k blocks and then partially order the blocks, n>=1, 1<=k<=n.

Original entry on oeis.org

1, 1, 3, 1, 9, 19, 1, 21, 114, 219, 1, 45, 475, 2190, 4231, 1, 93, 1710, 14235, 63465, 130023, 1, 189, 5719, 76650, 592340, 2730483, 6129859, 1, 381, 18354, 372519, 4442550, 34586118, 171636052, 431723379, 1, 765, 57475, 1701630, 29409681, 344040858, 2831994858, 15542041644, 44511042511

Offset: 1

Geoffrey Critzer, Nov 27 2014

T(n,k) is also the number of topologies U on an n-set such that a minimal basis for U contains exactly k sets. - Geoffrey Critzer, Dec 26 2016

T(n,k) is also the number of transitive, reflexive Boolean relation matrices on [n] that have exactly k strongly connected components. - Geoffrey Critzer, Feb 27 2023

			Triangle T(n,k) begins:
  1;
  1,   3;
  1,   9,   19;
  1,  21,  114,   219;
  1,  45,  475,  2190,   4231;
  1,  93, 1710, 14235,  63465,  130023;
  1, 189, 5719, 76650, 592340, 2730483, 6129859;
  ...

Alois P. Heinz, Rows n = 1..18

Row sums gives A000798, n >= 1.
Leading diagonal gives A001035, n >= 1.
Apparently column 2 gives the terms > 1 of A068156.

A001035 = Cases[Import["https://oeis.org/A001035/b001035.txt", "Table"], {, }][[All, 2]];
lg = Length[A001035];
A[x_] = Sum[A001035[[n + 1]] x^n/n!, {n, 0, lg - 1}];
Rest[CoefficientList[#, y]]& /@ (CoefficientList[A[y*(Exp[x] - 1)] + O[x]^lg, x]*Range[0, lg - 1]!) // Flatten (* Jean-François Alcover, Jan 01 2020 *)

E.g.f.: A(y*(exp(x) - 1)) where A(x) is the e.g.f. for A001035.

cp's OEIS Frontend

A295515 The Euclid tree, read across levels.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Sage

Formula

A099257 a(1)=1, a(n+1) = if a(n)=n then 2*n+1 else smallest number not occurring earlier.

Views

Author

Keywords

Comments

Links

Formula

A232598 T(n,k) = Stirling2(n,k) * OrderedBell(k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A330530 Lexicographically earliest sequence of distinct positive integers such that the product of two consecutive terms is always divisible by 4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A143088 Triangle T(n,m) = (2^(m+1) - 1) * (2^(n-m+1) - 1), read by rows, 0 <= m <= n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

A146884 a(n) = 7*Sum_{k=0..n} 6^k.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A146885 a(n) = 8*Sum_{k=0..n} 7^k.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A147758 Numbers whose binary representation is a palindrome formed from the reflected decimal expansion of the concatenation of 1, 0 and infinite digits 1.

Views

Author

Keywords

Comments

Crossrefs

Extensions

A175160 Primes p such that 2p+3, 4p+9, 8p+21, 16p+45, 32p+93 and 64p+189 are also prime.