Scholz’s Third Conjecture: A Demonstration for Star Addition Chains ()
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:
![](https://www.scirp.org/html/1-7401654\262584e0-2a3e-42ef-9825-84dc08fe6e91.jpg)
![](https://www.scirp.org/html/1-7401654\1149c03f-3d44-4deb-ae3f-996f524a803d.jpg)
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) ![](https://www.scirp.org/html/1-7401654\c02efadc-500e-4d48-84b7-e2663d2dfbff.jpg)
2) ![](https://www.scirp.org/html/1-7401654\eae10d7a-ce09-4793-9bbb-c6721da1d1f6.jpg)
Definition 3. Let ![](https://www.scirp.org/html/1-7401654\5f3b96d1-d26b-4a64-9af6-a080756627ab.jpg)
denote an addition chain of a number e, the highest index of the sequence r is called length of the chain Se, 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:
![](https://www.scirp.org/html/1-7401654\cd8581fa-5345-466a-b931-807a543e41a7.jpg)
2. Basic Properties
Proposition 1. Let
denote an addition chain of n; then, ![](https://www.scirp.org/html/1-7401654\91475ad0-67a7-454b-9b90-1cec7c5b5fef.jpg)
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
![](https://www.scirp.org/html/1-7401654\9d692ce8-8a5d-4744-8f82-72c1a2cc1792.jpg)
Q.E.D.
Proposition 2.
Let
denote a star addition chain of n, then:
where
(1)
It defines a star addition chain at ![](https://www.scirp.org/html/1-7401654\b765e580-2416-4f41-ad71-9a5855789abf.jpg)
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 ![](https://www.scirp.org/html/1-7401654\cfbc144d-4b36-472e-a412-3fb1204d190d.jpg)
2) Its last element is ![](https://www.scirp.org/html/1-7401654\e6aa146b-a066-4fc4-b15b-3a47bcaf94f8.jpg)
For each
and
the following is true:
![](https://www.scirp.org/html/1-7401654\f080ee2c-c54b-462f-8a42-fabf3df1fb8d.jpg)
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 ![](https://www.scirp.org/html/1-7401654\acd431df-0f29-40d1-9ea9-01d9a7b63504.jpg)
For
, j varies between
; as
is of star type, ![](https://www.scirp.org/html/1-7401654\bd453afc-e1d7-44aa-9117-2f8e08baee34.jpg)
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 ![](https://www.scirp.org/html/1-7401654\4ac73636-e20a-47d7-8afc-8251603caa72.jpg)
Q.E.D.
Proposition 3. The length of the addition chain of
defined by:
where
![](https://www.scirp.org/html/1-7401654\303417a3-9f24-4aac-ad21-a192d8f4be33.jpg)
Induced by the star addition chain
, it has length: ![](https://www.scirp.org/html/1-7401654\d1d8859d-5063-4ecb-97b0-e453eacaad32.jpg)
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 ![](https://www.scirp.org/html/1-7401654\a45a0826-afda-43f1-b67a-0b1bb22b0bbc.jpg)
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:
![](https://www.scirp.org/html/1-7401654\14532d3d-3528-4d8f-9c2f-ea477d7d094d.jpg)
since
and ![](https://www.scirp.org/html/1-7401654\a98ae3fc-36e1-433f-881f-5d4f86ad2811.jpg)
The number of elements of
as ![](https://www.scirp.org/html/1-7401654\3dc1ef53-3b26-4b66-9249-8ce4be5e6965.jpg)
(Proposition 1)
From where
since ![](https://www.scirp.org/html/1-7401654\4378b8b2-db70-411c-b5b7-d8a4ddd15308.jpg)
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 ![](https://www.scirp.org/html/1-7401654\823c3410-0f9c-4852-8e67-eb160dbc97c6.jpg)
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 ![](https://www.scirp.org/html/1-7401654\7fd0a4f2-ff75-4125-a036-756f600f57c5.jpg)
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 ![](https://www.scirp.org/html/1-7401654\fbc1a051-aac0-47c1-8e05-670a3e20e106.jpg)