A079301 -id:A079301 - cp's OEIS frontend

A079300 a(n) = number of shortest addition chains ending in n.

1, 1, 1, 1, 2, 2, 5, 1, 3, 4, 15, 3, 10, 14, 4, 1, 2, 7, 33, 6, 29, 40, 4, 4, 14, 24, 5, 23, 132, 12, 77, 1, 2, 4, 43, 12, 39, 92, 20, 8, 23, 84, 4, 69, 14, 8, 220, 5, 12, 36, 4, 38, 205, 16, 156, 32, 173, 352, 37, 24, 91, 233, 87, 1, 2, 4, 23, 6, 29, 134, 1258, 18, 49, 104, 32

Offset: 1

David W. Wilson, Feb 09 2003

nonn

An addition chain is a finite sequence of whole numbers starting with 1 in which each subsequent term is the sum of two (not necessarily distinct) earlier terms. - Glen Whitney, Nov 08 2021

			7 has a(7) = 5 shortest addition chains: (1,2,3,4,7), (1,2,3,5,7), (1,2,3,6,7), (1,2,4,5,7), (1,2,4,6,7).

Glen Whitney, Table of n, a(n) for n = 1..18286 (Terms 1..1024 from D. W. Wilson)
Achim Flammenkamp, Compressed table of a(n) (for all n such that A003313(n) < 23, including all n < 196591)
Achim Flammenkamp, Shortest addition chains
Eric Weisstein's World of Mathematics, Addition Chain
Glen Whitney, C program to compute counts of addition chains

Cf. A003313, A118386, A118387.

Cf. A079301, A079302, the number of shortest addition chains of Brauer and non-Brauer type, respectively.

a(n) = A079301(n) + A079302(n). - Glen Whitney, Nov 06 2021

More terms from Don Reble, Mar 31 2006

Name edited by Glen Whitney, Nov 08 2021

A060765 Numbers n such that every difference between consecutive divisors (ordered by increasing magnitude) of n is also a divisor of n.

Original entry on oeis.org

1, 2, 4, 6, 8, 12, 16, 18, 20, 24, 32, 36, 42, 48, 54, 60, 64, 72, 96, 100, 108, 120, 128, 144, 156, 162, 168, 180, 192, 216, 240, 256, 272, 288, 294, 300, 324, 342, 360, 384, 432, 480, 486, 500, 504, 512, 576, 600, 648, 720, 768, 840, 900, 960, 972, 1008, 1024

Offset: 1

Labos Elemer, Apr 24 2001

nonn

Equivalently, A060763(n)=0.
Powers of 2 and factorials up to 7! are here.
For each k=1..A000005(a(n))-1 exists k' < A000005(a(n)) such that A193829(a(n),k) = A027750(a(n),k'). - Reinhard Zumkeller, Jun 25 2015
From Robert Israel, Jul 03 2017: (Start)
Also includes 3*2^k and 2*3^k for all k>= 1.
All terms except 1 are even. (End)
Conjecture: a(n) has the property that for each prime divisor p, p-1|a(n)/p. If this conjecture is true then terms can be searched by distinct prime divisors. - David A. Corneth, Jul 06 2017
The divisors of a(n) form a Brauer chain. See A079301 for the definition of a Brauer chain. - Zizheng Fang, Jan 30 2020

			For n = 12, divisors={1, 2, 3, 4, 6, 12}; differences={1, 1, 1, 2, 6}; every difference is a divisor, so 12 is in the sequence.

Donovan Johnson, Table of n, a(n) for n = 1..750

Cf. A060683, A060763, A193829, A027750.

import Data.List (sort, nub); import Data.List.Ordered (subset)
a060765 n = a060765_list !! (n-1)
a060765_list = filter
(\x -> sort (nub $ a193829_row x) `subset` a027750_row' x) [1..]
-- Reinhard Zumkeller, Jun 25 2015

[k:k in [1..1025]| forall{i:i in [2..#Divisors(k)]|k mod (d[i]-d[i-1]) eq 0 where d is Divisors(k)}]; // Marius A. Burtea, Jan 30 2020

f:= proc(n) local D,L;
  D:= numtheory:-divisors(n);
  L:= sort(convert(D,list));
  nops(convert(L[2..-1]-L[1..-2],set) minus D);
end proc:
select(f=0, [$1..1000]); # Robert Israel, Jul 03 2017

test[n_ ] := Length[Complement[Drop[d=Divisors[n], 1]-Drop[d, -1], d]]==0; Select[Range[1, 1024], test]
(* Second program: *)
Select[Range[2^10], Function[n, AllTrue[Differences@ Divisors@ n, Divisible[n, #] &]]] (* Michael De Vlieger, Jul 12 2017 *)

isok(n)=my(d=divisors(n), v=vecsort(vector(#d-1, k, d[k+1]-d[k]),,8)); #select(x->setsearch(d, x), v) == #v; \\ Michel Marcus, Jul 06 2017

is(n)=my(t); fordiv(n,d, if(n%(d-t), return(0)); t=d); 1 \\ Charles R Greathouse IV, Jul 12 2017

Edited by Dean Hickerson, Jan 22 2002

A008928 Number of increasing sequences of addition chain type with maximal element n.

Original entry on oeis.org

1, 1, 1, 2, 3, 6, 10, 21, 38, 77, 144, 293, 563, 1131, 2205, 4434, 8711, 17466, 34506, 69169, 137247, 274677, 546081, 1093217, 2177556, 4356756, 8688370, 17381926, 34691608, 69394626, 138578144, 277197191, 553794526, 1107654097, 2213527055, 4427345544, 8849519773

Offset: 1

Mauro Torelli (torelli(AT)hermes.mc.dsi.unimi.it)

nonn

This sequence counts all addition chains for n. - David W. Wilson, Apr 01 2006

In other words, a(n) = the number of increasing addition chains ending in n. - Don Reble, Apr 09 2006

Martin Fuller, Table of n, a(n) for n = 1..64
Don Reble, Python program
Mauro Torelli, Increasing integer sequences and Goldbach's conjecture, RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, 40:2 (2006), pp. 107-121.

Cf. A008927, A079301, A008933.

More terms from David W. Wilson, Apr 01 2006

More terms from Don Reble, Apr 09 2006

A008927 Number of increasing sequences of star chain type with maximal element n.

Original entry on oeis.org

1, 1, 1, 2, 3, 6, 10, 20, 36, 70, 130, 252, 475, 916, 1745, 3362, 6438, 12410, 23852, 46020, 88697, 171339, 330938, 640189, 1238751, 2399677, 4650819, 9021862, 17510819, 34013311, 66106491, 128568177, 250191797, 487168941, 949133722, 1850211247, 3608650388

Offset: 1

Mauro Torelli (torelli(AT)hermes.mc.dsi.unimi.it)

nonn

a(n) counts the Brauer addition chains for n, which are equivalent to star chains. In a Brauer chain, each element after the first is the sum of any previous element with the immediately previous element. This sequence counts all Brauer chains for n, not just the minimal ones, which are given by A079301. - David W. Wilson, Apr 01 2006

In other words, a(n) = the number of increasing star addition chains ending in n.

			a(5)=3 because 1,2,3,4,5; 1,2,3,5; 1,2,4,5 are star-kind addition chains.
a(8)=20 because there are 21 increasing addition chains up to 8, but 1,2,4,5,8 is not a star chain.

M. Torelli, Increasing integer sequences and Goldbach's conjecture, preprint, 1996.
D. E. Knuth, The Art of Computer Programming; Addison-Wesley. Section 4.6.3.

Martin Fuller, Table of n, a(n) for n = 1..70
M. Torelli, Increasing integer sequences and Goldbach's conjecture, RAIRO - Theoretical Informatics and Applications, vol.40, no.02 (April 2006), pp.107-121.

Cf. A008928, A079301.

Conjecture: a(n) ~ 2^n/n. - Martin Fuller, Apr 29 2025

More terms from David W. Wilson, Apr 01 2006

A118844 Numbers that have only Brauer chains as shortest addition chains.

Original entry on oeis.org

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 20, 22, 23, 24, 27, 28, 30, 32, 33, 34, 35, 36, 40, 43, 44, 45, 46, 48, 51, 54, 56, 60, 64, 65, 66, 67, 68, 70, 72, 77, 80, 83, 85, 86, 88, 90, 92, 96, 99, 102, 108, 112, 119, 120, 128, 129, 130, 131, 132, 134, 135, 136

Offset: 1

Hugo Pfoertner, May 01 2006

nonn

Indices of zeros in A079302. See A079301 for the definition of a Brauer addition chain.

Giovanni Resta, Tables of Shortest Addition Chains, computed by David W. Wilson.

Cf. A079301 (number of minimal Brauer chains for n), A079302 (number of minimal non-Brauer chains for n), A118845 (numbers with shortest non-Brauer chains).

A118845 Numbers that have non-Brauer chains among their shortest addition chains.

Original entry on oeis.org

13, 19, 21, 25, 26, 29, 31, 37, 38, 39, 41, 42, 47, 49, 50, 52, 53, 55, 57, 58, 59, 61, 62, 63, 69, 71, 73, 74, 75, 76, 78, 79, 81, 82, 84, 87, 89, 91, 93, 94, 95, 97, 98, 100, 101, 103, 104, 105, 106, 107, 109, 110, 111, 113, 114, 115, 116, 117, 118, 121, 122, 123

Offset: 1

Hugo Pfoertner, May 01 2006

nonn

Indices of nonzero terms in A079302. See A079301 for the definition of a Brauer addition chain.

Giovanni Resta, Tables of Shortest Addition Chains, computed by David W. Wilson.

Cf. A118846 (corresponding counts of minimal non-Brauer chains), A079301 (number of minimal Brauer chains for n), A079302 (number of minimal non-Brauer chains for n), A118844 (numbers without shortest non-Brauer chains).

A349044 Non-Brauer numbers.

Original entry on oeis.org

12509, 13207, 13705, 15473, 16537, 20753, 22955, 23219, 23447, 24797, 25018, 26027, 26253, 26391, 26414, 26801, 27401, 27410, 30897, 30946, 31001, 32921, 33065, 33074, 41489, 41506, 43755, 43927, 45867, 46355, 46419, 46797, 46871, 46894, 47761, 49373, 49577, 49593, 49594, 49611, 50036, 50829, 51667

Offset: 1

Glen Whitney, Nov 06 2021

nonn

A sequence 1=a_0 < a_1 < a_2 < ... < a_l = n is an addition chain (of length l) for n if for each i, 0 < i <= l, there are j_i and k_i such that a_i = a_j_i + a_k_i. Such a chain is called a star-chain or Brauer chain if in addition each j_i = i-1. A number is a Brauer number if among its shortest addition chains there is a Brauer chain, and non-Brauer otherwise.
The length of a shortest Brauer chain for n is often denoted l^*(n). A003313(n) gives the length of a shortest addition chain for n. Thus n is in this sequence if and only if A003313(n) < l^*(n).
For entries at least through 41506, these numbers satisfy l^*(n) = A003313(n) + 1. It seems likely that larger differences between l^*(n) and A003313(n) occur for later entries in this sequence, but it is unclear whether any n with a larger difference have been found.
These differences between l^*(n) and A003313(n) are highlighted by the following formulation: consider a machine which starts with a 1 in "cache" and can then at each step execute one of two operations: (1) Add any number that has ever been in cache to the current contents of cache, or (2) Restore any number that has previously been in cache to the cache, replacing its prior contents. Then n is in this sequence if and only if there is a shortest program that results in n in cache that includes a "Restore" step. Note further that if there is an entry in this sequence such that l^*(n) > A003313(n)+1, then all shortest programs producing n in cache would contain a "Restore" operation. The definition of A293771 is based on a similar machine with a separate "Store" operation that puts the cache value into "memory," and one could formulate an analogous conjecture here that the "Restore" operation is never necessary for a shortest program. The existence or not of an n in this sequence such that l^*(n) > A003313(n)+1 would settle this question and provide mild evidence one way or the other on the conjecture in A293771.

			The shortest star-chains for 12509 have length 18; one example is 1,2,3,4,7,11,18,25,43,86,172,344,688,1376,1401,2777,5554,6955,12509. (By inspection, each number in this chain is the sum of the prior number and another number in the sequence, possibly also the prior number.) On the other hand, there are addition chains of length 17 for 12509, e.g., 1,2,4,6,12,13,24,48,96,192,384,768,781,1562,3124,6248,12496,12509. (Here a_5 = a_3+a_3, preventing this from being a star-chain.) All numbers smaller than 12509 include a star chain among their shortest addition chains (by exhaustive search). Hence 12509 is the first number in this sequence.

Harry Altman, Integer Complexity, Addition Chains, and Well-Ordering, Ph.D. thesis, 2014.
Neill Clift, Addition Chains
W. Hansen, Zum Scholz-Brauerschen Problem, J. Reine Angew. Math. 202 (1959), 129-136.

Cf. A003313, the length of a shortest addition chain for n.

Cf. A079301, A079302, the number of shortest addition chains for n which are Brauer chains and which are non-Brauer chains, respectively.

A079301(n) = 0 if and only if n occurs in this sequence.

A118846 Number of non-Brauer chains corresponding to the entries of A118845.

Original entry on oeis.org

1, 2, 3, 1, 2, 18, 13, 6, 5, 2, 3, 6, 37, 1, 2, 3, 34, 17, 25, 44, 4, 15, 32, 7, 3, 244, 7, 13, 2, 8, 6, 129, 3, 6, 9, 73, 77, 69, 45, 90, 13, 1, 2, 3, 49, 15, 4, 46, 81, 4, 25, 44, 13, 20, 62, 3, 73, 7, 9, 20, 35, 7, 52, 4, 20, 674, 3, 3, 6, 163, 403, 673, 124, 8, 15, 2, 20, 6, 157, 11

Offset: 1

Hugo Pfoertner, May 01 2006

nonn

See A079301 for the definition of a Brauer addition chain.

			a(3)=3 because there exist 3 different non-Brauer shortest addition chains for n=A118845(3)=21: [1 2 4 5 8 13 21] and [1 2 4 5 8 16 21] with 8=4+4 (5 not part of sum), [1 2 4 8 9 12 21] with 12=8+4 (9 not part of sum).

Giovanni Resta, Tables of Shortest Addition Chains, computed by David W. Wilson.

Cf. A118845 [numbers with shortest non-Brauer chains], A079301 [Number of minimal Brauer chains for n], A079302 [Number of minimal non-Brauer chains for n], A118844 [numbers without shortest non-Brauer chains].

A086833 Minimum number of different addends occurring in any shortest addition chain of Brauer type for a given n, or 0 if n has no shortest addition chain of Brauer type.

Original entry on oeis.org

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

Offset: 1

Tatsuru Murai, Aug 08 2003

nonn

n = 12509 is the first n for which a(n) = 0 because it is the smallest number that has no shortest addition chain of Brauer type. - Hugo Pfoertner, Jun 10 2006 [Edited by Pontus von Brömssen, Apr 25 2025]

			a(23)=5 because 23=1+1+2+1+4+9+5 is the shortest addition chain for 23.
For n=9 there are A079301(9)=3 different shortest addition chains, all of Brauer type:
[1 2 3 6 9] -> 9=1+1+1+3+3 -> 2 different addends {1,3}
[1 2 4 5 9] -> 9=1+1+2+1+4 -> 3 different addends {1,2,4}
[1 2 4 8 9] -> 9=1+1+2+4+1 -> 3 different addends {1,2,4}
The minimum number of different addends is 2, therefore a(9)=2.

Giovanni Resta, Tables of Shortest Addition Chains, computed by David W. Wilson.
Index to sequences related to the complexity of n

Cf. A003064, A003065, A003313, A005766, A008057, A008928, A008933, A079300, A079300, A079301, A349044.

a(n) = 0 if and only if n is in A349044. - Pontus von Brömssen, Apr 25 2025

Edited by Hugo Pfoertner, Jun 10 2006

Escape clause added by Pontus von Brömssen, Apr 25 2025

cp's OEIS Frontend

A079300 a(n) = number of shortest addition chains ending in n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A060765 Numbers n such that every difference between consecutive divisors (ordered by increasing magnitude) of n is also a divisor of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Extensions

A008928 Number of increasing sequences of addition chain type with maximal element n.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A008927 Number of increasing sequences of star chain type with maximal element n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A118844 Numbers that have only Brauer chains as shortest addition chains.

Views

Author

Keywords

Comments

Links

Crossrefs

A118845 Numbers that have non-Brauer chains among their shortest addition chains.

Views

Author

Keywords

Comments

Links

Crossrefs

A349044 Non-Brauer numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A118846 Number of non-Brauer chains corresponding to the entries of A118845.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A086833 Minimum number of different addends occurring in any shortest addition chain of Brauer type for a given n, or 0 if n has no shortest addition chain of Brauer type.

Views

Author