Scholz’s Third Conjecture: A Demonstration for Star Addition Chains ()

José Maclovio Sautto Vallejo, Agustín Santiago Moreno, Carlos N. Bouza Herrera, Verónica Campos Guzmán

Facultad de Matemática y Computación, Universidad de la Habana, Ciudad de La Habana, Cuba.

Facultad de Matemáticas, Universidad Autónoma de Guerrero, Guerrero, México.

Universidad Autónoma de Guerrero, Unidad Académica de Ciencias y Tecnologías de la Información, Guerrero, México.

**DOI: **10.4236/am.2013.410A1001
PDF
HTML XML
3,290
Downloads
5,006
Views
Citations

Facultad de Matemática y Computación, Universidad de la Habana, Ciudad de La Habana, Cuba.

Facultad de Matemáticas, Universidad Autónoma de Guerrero, Guerrero, México.

Universidad Autónoma de Guerrero, Unidad Académica de Ciencias y Tecnologías de la Información, Guerrero, México.

This paper presents a brief demonstration of Scholz’s third conjecture [1] for n numbers such that their minimum chain addition is star type [2]. The demonstration is based on the proposal of an algorithm that takes as input the star-adding chain of a number n, and returns a string in addition to *x* = 2^{n} - 1 of length equal to *l *(*n*) + *n* - 1. As for any type addition chain star of a number n, this chain is minimal demonstrates the Scholz’s third Conjecture for such numbers.

Share and Cite:

Vallejo, J. , Moreno, A. , Herrera, C. and Guzmán, V. (2013) Scholz’s Third Conjecture: A Demonstration for Star Addition Chains. *Applied Mathematics*, **4**, 1-2. doi: 10.4236/am.2013.410A1001.

1. Basic Definitions

Definition 1. Let denote a finite sequence of natural numbers. We will call it an addition chain of a natural number e if it satisfies:

Definition 2. Let denote a finite sequence of natural numbers. We will call it a star addition chain of a natural number e if it satisfies:

1)

2)

Definition 3. Let

denote an addition chain of a number e, the highest index of the sequence r is called length of the chain S_{e}, and it is represented by .

Definition 4. The **minimum length** of all addition chains of a natural number e is denoted by l(e), that is:

2. Basic Properties

*Proposition 1.* Let denote an addition chain of n; then,

**Proof:**

Clearly, since the terms’ sub-indexes start at zero and end at k. Now, by definition, the length of the addition chain is the last sub-index, which implies

*Q.E.D.*

*Proposition 2.*

Let denote a star addition chain of n, then:

where

(1)

It defines a star addition chain at

**Proof:**

Let denote an addition chain of n of type *of length p, then the sequence defined in (1) fulfills the following properties:

1) Its first element is

2) Its last element is

For each and the following is true:

That is, is of the star type for, since it is equal to the sum repeated from the previous to it in the sequence.

Now we will prove that the elements for are of the star type, since we have already proved that it is equal to 1 for the case.

By definition, we obtain from (1) that

for any, since is of the star type

For, j varies between; as is of star type,

From where; is the maximum value of j for, which proves that; where is the maximum value of j corresponding to, that is, the former to , which completes our demonstration: the sequence is a star addition chain of

*Q.E.D.*

*Proposition 3.* The length of the addition chain of defined by:

where

Induced by the star addition chain , it has length:

**Proof:**

Let denote a star sequence of n; we will assume without loss of generality that , then the sequence has odd values, which corresponds to the where

The even elements of are given by the differences of for each i from zero until p − 1, the said sum of values is equal to:

since and

The number of elements of

as

(*Proposition 1*)

From where since

*Q.E.D.*

3. Scholz’s Third Conjecture: A Demonstration for Star Addition Chains

*Theorem. *Let denote a minimal star addition chain of n, then

**Proof:**

As is a minimal addition chain and is also of the star type, Proposition 2 guarantees us the existence of an addition chain at, Proposition 3 guarantees us that that chain has a length equal to, which proves that

*Q.E.D.*

At UACyTI’s website

www.uacyti.uagro.net/3aconjetura an implementation in PHP of this algorithm can be found. It has a star addition chain of a natural number n as input, then it verifies that it is truly a star addition chain; if it is not, input is rejected, if it is, it generates the star addition chain of of length

Conflicts of Interest

The authors declare no conflicts of interest.

Journals Menu

Contact us

+1 323-425-8868 | |

customer@scirp.org | |

+86 18163351462(WhatsApp) | |

1655362766 | |

Paper Publishing WeChat |

Copyright © 2024 by authors and Scientific Research Publishing Inc.

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.