Addition chain (original) (raw)
In mathematics, an addition chain for computing a positive integer n can be given by a sequence of natural numbers starting with 1 and ending with n, such that each number in the sequence is the sum of two previous numbers. The length of an addition chain is the number of sums needed to express all its numbers, which is one less than the cardinality of the sequence of numbers.
| Property | Value |
|---|---|
| dbo:abstract | In mathematics, an addition chain for computing a positive integer n can be given by a sequence of natural numbers starting with 1 and ending with n, such that each number in the sequence is the sum of two previous numbers. The length of an addition chain is the number of sums needed to express all its numbers, which is one less than the cardinality of the sequence of numbers. (en) Eine Additionskette für eine positive ganze Zahl ist eine endliche Folge positiver ganzer Zahlen, die mit 1 beginnt und mit endet und bei der jede Zahl der Folge außer der 1 die Summe zweier nicht notwendig verschiedener vorangegangener Folgenglieder ist. Für fast alle Fragestellungen genügt es, streng monoton steigende Folgen zu betrachten, so dass die Monotonie oft mit gefordert wird (siehe ). Unter der Länge einer Additionskette versteht man die Anzahl der Folgenglieder, die Summe vorangegangener Folgenglieder sind – die 1 am Anfang wird also nicht mitgezählt. Ist die Länge der Additionskette für , so ist . Die minimale Länge aller Additionsketten für wird mit bezeichnet. Beispiel: * (1, 2, 4, 5, 9) ist eine Additionskette der Länge 4 für 9, denn 2 = 1+1, 4 = 2+2, 5 = 4+1 und 9 = 5+4. * (1, 2, 4, 6, 9) ist keine Additionskette für 9, denn 9 ist nicht Summe zweier vorangegangener Folgenglieder. , denn es gibt keine kürzere Additionskette für 9. Andere Additionsketten für 9 sind gleich lang (zwei weitere) oder länger. (de) En matemáticas una suma encadenada es una secuencia a0, a1, a2, a3, ... que satisface: a0 = 1, ypara cada k>0: ak = ai + aj para algún i, j < k. Como ejemplo: 1, 2, 3, 6, 12, 24, 30, 31 es una suma encadenada para 31, de longitud 7, entonces: 2 = 1 + 13 = 2 + 16 = 3 + 312 = 6 + 624 = 12 + 1230 = 24 + 631 = 30 + 1 Las sumas encadenadas se emplean en la potenciación: de esta forma, por ejemplo, sólo necesitamos 7 multiplicaciones para calcular 531: 52 = 51 × 5153 = 52 × 5156 = 53 × 53512 = 56 × 56524 = 512 × 512530 = 524 × 56531 = 530 × 51 (es) En mathématiques, et particulièrement en arithmétique, une chaîne d'additions pour le calcul d'un entier positif n est une suite d'entiers naturels commençant par 1 et se terminant par n, et telle que chaque entier de la suite est la somme de deux entiers précédents. La longueur de la chaîne d'additions est le nombre de sommes nécessaires pour exprimer ces entiers ; c'est un de moins que le nombre de termes dans la suite. (fr) Аддитивная цепочка — последовательность натуральных чисел, начинающаяся с единицы, в которой каждый последующий элемент является суммой каких-то двух предшествующих элементов (в том числе, возможно использование одного и того же предшествующего элемента — удвоение). Формально, в аддитивной последовательности выполнены условия: * ; * для любого , , где . Одной из практически интересных разновидностей аддитивной цепочки является цепочка, заканчивающаяся числом , в которой каждый последующий элемент является удвоением предыдущего или суммой предыдущего и первого элементов: * для любого , или . Такая цепочка соответствует последовательности операций при возведении в степень «слева направо» (удвоение показателя степени соответствует возведению в квадрат, прибавление единицы — умножению на основание). Пример такой цепочки для : 1, 2 = 1+1, 4 = 2+2, 5 = 4+1, 10 = 5+5. (ru) |
| dbo:wikiPageExternalLink | http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html http://www.numdam.org/item%3Fid=JTNB_1994__6_1_21_0 |
| dbo:wikiPageID | 578656 (xsd:integer) |
| dbo:wikiPageLength | 9212 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1082366656 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Scholz_conjecture dbr:Mathematics dbr:Vectorial_addition_chain dbr:Conjecture dbr:Arnold_Scholz dbr:Hamming_weight dbr:Addition-chain_exponentiation dbr:Addition-subtraction_chain dbc:Addition_chains dbr:Exponentiation dbr:Exponentiation_by_squaring dbr:Cardinality dbr:Lucas_chain dbr:Bulletin_of_the_American_Mathematical_Society dbr:Natural_number dbr:Sequence dbr:Springer-Verlag dbr:Prime_factorization |
| dbp:name | Length of shortest addition chain for n (en) |
| dbp:sequencenumber | A003313 (en) |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Cite_journal dbt:Main dbt:Math dbt:Mvar dbt:OEIS dbt:OEIS_el dbt:Reflist dbt:Tmath |
| dcterms:subject | dbc:Addition_chains |
| gold:hypernym | dbr:Sum |
| rdf:type | yago:Abstraction100002137 yago:Company108058098 yago:Group100031264 yago:Institution108053576 yago:Organization108008335 yago:YagoLegalActor yago:YagoLegalActorGeo yago:YagoPermanentlyLocatedEntity dbo:Settlement yago:SocialGroup107950920 yago:WikicatAdditionChains |
| rdfs:comment | In mathematics, an addition chain for computing a positive integer n can be given by a sequence of natural numbers starting with 1 and ending with n, such that each number in the sequence is the sum of two previous numbers. The length of an addition chain is the number of sums needed to express all its numbers, which is one less than the cardinality of the sequence of numbers. (en) En matemáticas una suma encadenada es una secuencia a0, a1, a2, a3, ... que satisface: a0 = 1, ypara cada k>0: ak = ai + aj para algún i, j < k. Como ejemplo: 1, 2, 3, 6, 12, 24, 30, 31 es una suma encadenada para 31, de longitud 7, entonces: 2 = 1 + 13 = 2 + 16 = 3 + 312 = 6 + 624 = 12 + 1230 = 24 + 631 = 30 + 1 Las sumas encadenadas se emplean en la potenciación: de esta forma, por ejemplo, sólo necesitamos 7 multiplicaciones para calcular 531: 52 = 51 × 5153 = 52 × 5156 = 53 × 53512 = 56 × 56524 = 512 × 512530 = 524 × 56531 = 530 × 51 (es) En mathématiques, et particulièrement en arithmétique, une chaîne d'additions pour le calcul d'un entier positif n est une suite d'entiers naturels commençant par 1 et se terminant par n, et telle que chaque entier de la suite est la somme de deux entiers précédents. La longueur de la chaîne d'additions est le nombre de sommes nécessaires pour exprimer ces entiers ; c'est un de moins que le nombre de termes dans la suite. (fr) Eine Additionskette für eine positive ganze Zahl ist eine endliche Folge positiver ganzer Zahlen, die mit 1 beginnt und mit endet und bei der jede Zahl der Folge außer der 1 die Summe zweier nicht notwendig verschiedener vorangegangener Folgenglieder ist. Für fast alle Fragestellungen genügt es, streng monoton steigende Folgen zu betrachten, so dass die Monotonie oft mit gefordert wird (siehe ). Beispiel: , denn es gibt keine kürzere Additionskette für 9. Andere Additionsketten für 9 sind gleich lang (zwei weitere) oder länger. (de) Аддитивная цепочка — последовательность натуральных чисел, начинающаяся с единицы, в которой каждый последующий элемент является суммой каких-то двух предшествующих элементов (в том числе, возможно использование одного и того же предшествующего элемента — удвоение). Формально, в аддитивной последовательности выполнены условия: * ; * для любого , , где . Одной из практически интересных разновидностей аддитивной цепочки является цепочка, заканчивающаяся числом , в которой каждый последующий элемент является удвоением предыдущего или суммой предыдущего и первого элементов: * для любого , или . (ru) |
| rdfs:label | Additionskette (de) Addition chain (en) Suma encadenada (es) Chaîne d'additions (fr) Аддитивная цепочка (ru) |
| owl:sameAs | freebase:Addition chain yago-res:Addition chain wikidata:Addition chain dbpedia-de:Addition chain dbpedia-es:Addition chain dbpedia-fr:Addition chain dbpedia-ru:Addition chain dbpedia-vi:Addition chain https://global.dbpedia.org/id/4LRCy |
| prov:wasDerivedFrom | wikipedia-en:Addition_chain?oldid=1082366656&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Addition_chain |
| is dbo:wikiPageRedirects of | dbr:Addition_Chain dbr:Brauer_chain dbr:Brauer_number |
| is dbo:wikiPageWikiLink of | dbr:List_of_computability_and_complexity_topics dbr:Scholz_conjecture dbr:Alfred_Brauer dbr:Index_of_combinatorics_articles dbr:Vectorial_addition_chain dbr:Addition-chain_exponentiation dbr:Addition-subtraction_chain dbr:Addition_Chain dbr:Exponentiation_by_squaring dbr:List_of_NP-complete_problems dbr:Lucas_chain dbr:List_of_unsolved_problems_in_mathematics dbr:Nonhypotenuse_number dbr:Brauer_chain dbr:Brauer_number |
| is foaf:primaryTopic of | wikipedia-en:Addition_chain |