k-similarity of additive sequences

[See

Arithmetic self-similarity of additive sequences

for updated version of this page.]

Arithmetic self-similarity of additive sequences

Properties of completely additive sequences
Examples

[To Do: Link list.]

Morphisms with fixed points that are completely additive sequences
Coprime generation of additive sequences
Proofs

Prime_generated_sequences_are_completely additive
Construction of all completely additive sequences

Miscellaneous
References

Properties of completely additive sequences

There is an infinite set of j-symbol sequences {S_j(n)} each of which has remarkable self-similarities: all arithmetic subsequences S_j( k*n ), obtained by taking every k-th entry, are either S_j(n) iteslf or (S_j(n) + c) modulo j, a shift of every element by an integer constant. This integer constant is simply the first element of the subsequence; c = S_j(k).

[To Do: Simple graphic.]

This self-similarity property can be stated as:

S_j(k*n) = ( S_j(n) + S_j(k) ) mod j

where j, and k are any particular positive integers, and n includes all positive integers. S_j(k) is the (single) k-th element of S_j(n), and + is element-wise addition at every index n of the sequence(s). For sequences on the field of natural numbers, or implicitly operating on a finite ring, we can drop the modulo operation and the j notation:

S(k*n)

 = S(n)
+ S(k)

These sequences are described as completely additive (and completely additive arithmetic functions), or totally additive (by analogy with totally multaplicative), because S(a*b) = S(a) + S(b) for every integer a and b. Sometimes they are described as pseudo-logarithmic because log(a*b) = log(a) + log(b) for any numbers a and b.\

There is a unique completely additive sequence that can be derived from every unique sequence S_p(m), and for every positive integer j. Call the sequence S_p(m) the prime generating sequence. The element of the corresponding completely additive sequence at the mth prime index, S_j(p_m), is the element of the prime generating sequence at m, S_p(m) mod j. The elements of S_j(n) where n is a compound number depends only on the (unique) prime factorization of n:



n = p₁^q * p₂^r * p₃^s
...

and

S_j(n) = ( q*S(p₁

)
+

r*S(p₂)

s*S(p₃

) ) mod j

= ( q*S_p(1

)
+

r*S_p(2)

s*S_p(3

) ) mod j

For example, choosing the prime generating sequence as the ordered integers S_p(m) = 1,2,3,4,5, ..., the corresponding completely additive sequence, over all integers, is:



n    = 1  2
 3  4  5  6  7  8  9 10 11 12

S(n) = 0  1  2  2  3  3  4  3  4  4
 5  4 ...
where the prime index elements are underlined.

The sequence elements at prime indices are the integers, in order. The 0-th element is zero (1 is any prime raised to the zeroth power). At the compound indices:

n = 4  = 2²
,

S( 4) =

2*S(2)      
            = 2

n = 6 = 2¹3¹,

S(
6) =

1*S(2) + 1*S(3)

= 3

n = 8  = 2³
,

S( 8) =

3*S(2)

= 3

n = 9  = 3²
,

S( 9) =

2*S(3)

= 4

n = 10 = 2¹5¹, S(10) = 1*S(2)

1*S(5)

=
4

n = 12 = 2²3¹, S(12) = 2*S(2)

1*S(3)

=
4

...

The sequences for which elements at prime indices are all zero except for the m-th prime element which is 1, S_p(m) = 0, 0, ... 1, ... 0, 0, ..., form a basis set of sequences. These "single-prime sequences", S(n | p_m=1) are constructed in the same way, so that:

The n-th element S(n|p_m=1)


is the number of
times the m-th prime,

p_m,

 is
a factor of
the index n.

[To Do: For example, the period-doubling sequence...]

Every completely additive sequence can be constructed as a linear combination of single-prime sequences. For the example above, generated from integers S_p(m) = 1,2,3,4,5, ...:

S(n) = 1*S( n | p₁=1

)
+

2*S(

n |

p₂=1 )

3*S(

n |

p₃=1

) ...,
where *,+ indicates element-wise
multiplication and addition of sequences



         1*S(

n|p₁=1

)
=

1*(
0  1  0  2  0  1  0  3  0  1
 0  2 ... )

       
 2*S(

n|p₂=1) =

2*(

0  0
 1  0  0  1  0  0  2  0
 0  1


... )

       
 3*S(

n|p₃=1) =

3*(

0  0
 0  0  1  0  0  0  0  1
 0  0


... )



         4*S(

n|p₄=1

)
=

4*(

0  0
 0  0  0  0  1  0  0  0
 0  0


... )

5*S(n|p₅=1

)
=

5*(

0  0  0  0  0  0  0  0  0  0
 1  0


... )

               ...

+ ____________________________________________________________

S(n) =

           
            0  1
 2  2  3  3  4  3  4  4
 5  4 ...

    Furthermore, this linear combination is unique. Any sequence that is completely additive is uniquely identified by j and the sequence of elements at prime indices.

    There's an elegant explanation for the relationship between these self-similar sequences and their prime sets. Taking every k-th element of a sequence is equivalent to the mapping n' = k*n so that the prime factors of n' always match those of n with the addition of the (constant) number of prime factors of k. The number of prime factors of n follow a non-periodic pattern as do the number of any subset of prime factors, so the factors of k*n follow the same pattern with only a constant added.

    There are also nice relationships between the sequences in the subsets {S_j(n), with j fixed}. With the definition of an addition operation between a pair of sequences (+, element wise addition modulo j) the sets form semigroups. With the inclusion of an identity element (the sequence S(n) = 0) the sets form monoids. For a finite j, each of these sets of sequences form a finite ring.

[To Do: Dimitri Hendricks has a nice way of thinking about the range of arithmetic self-similarities within these and other sequences. The coefficients a' and b' such that:

S(a'*n + b') = S(n) + c'

describe the arithmetic self-similarities and can (always?) be formed by composition from a smaller set of base coefficients, {a, b, c}. For the prime generated sequences the coefficients can be described in terms of only a prime integer, p, and the pth element of the sequence, S(p). In this way each prime generated sequence, with a countably infinite number of elements, are analogous to whole numbers in that prime numbers also form the basis of the countably infinite numbers. This is just a different way of saying that every kth element is self-similar to the sequence itself, but the idea of a base set of coefficients can be applied to sequences with other self-similarity properties. For example the Thue-Morse sequence is described (he thinks) by a base set with only three members.]

[To Do: Do all of these sequences avoid repetitions in arithmetic progressions? See Words avoiding repetitions in arithmetic progressions, J.-Y. Kao et al.]

Examples

A few examples are given here to clarify these relationships, and to cross reference with other methods of generating the the same sequences.

This chart lists, for each positive integer n (top row) the prime factorization (second row), and the integer power(s) of some factors:

n:        
     1    2    3    4
   5  
 6    7
   8  
 9   10   11
  12   13
  14   15
  16   17
  18  ...

prime factors:       2¹   3¹
  2²   5¹   2¹3¹
 7¹   2³    3²
 2¹5¹  11¹  2²3¹
13¹  2¹7¹  3¹5¹
 2⁴   17¹  2¹3²
...

for S_p(m) = 1
 0  0  0 ...

powers of 2's




in prime

 

factors of n =  0    1    0  
 2    0
   1    0
   3
   0    1    0    2  
 0    1
   0    4    0
   1  ...

(OEIS A007814 the binary carry sequence, the ruler function OEIS A001511 - 1, or the greatest k such that 2^k divides n, or the 2-adic valuation of n.)

for S_p(m) = 0
 1  0  0 ...

powers of 3's




in prime

 

factors

of n =

0    0    1  
 0    0
   1    0
   0
   2    0    0    1  
 0    0
   1    0    0
   2  ...

(OEIS A007949, or the greatest k such that 3^k divides n, or the 3-adic valuation of n. )

for S_p(m) = 1
 1  0  0 ...

power

s of 2's and powers
of 3's
in 

prime

factors

(sum of the two rows 

above)

of n =

0    1  
 1    2
   0  
 2    0
   3    2    1    0  
 3    0
   1    1    4
   0  
 3  ...



for S_p(m) = 1
 1  1  1 ...

the sum of all powers in prime



factors

of n =

  0  
 1    1  
 2    1
   2    1
   3
   2    2    1    3  
 1    2
   2    4    1
   3  ...

(OEIS A001222, or Omega(n). The Liouville function(n) = -1^Omega(n) = A008836. Note that Sp(m) = 1,1,1, ....)

j = 2, S_p(m) = 1,0,0,0... or p₁ = 1

This is a binary sequence (j = 2), where the n-th element is the parity of the powers of 2 in the prime factorization of n.

S₂(n)


  =  0    1
   0  
 0  
 0    1
   0  
 1    0
   1    0    0    0  
 1    0    0    0    1
 ...

(OEIS A096268, the period-doubling sequence, and its complement A035263)

We can check that the k-similarity property holds for a few k and for the first several k*n.

For k = 2, the k*n-th elements are:

S₂(2*n) =  1
   0    1    1    1  
 0    1    0    1
 ...

(OEIS A035263)

S₂(2*n) =

(
S₂(n) + S₂(2)
) mod 2, where

S₂(2)

= 1

For k = 3:

S₂(3*n) =  0
   1    0    0    0  
 1  ...

S₂(3*n) =

S₂(n)
=

( S₂(n)
+ 0 ) mod 2

For k = 4:

S₂(4*n) =  0
   1    0    0  ...

S₂(4*n) =

S₂(n)
=

( S₂(n)
+ 0 ) mod 2

j = 3, S_p(m) = 1,0,0,0... or p₁ = 1

This is a trinary sequence (j = 3), where the n-th element is the number of 2's in the factorization of n modulo 3.

S₃(n)

0    1    0  
 2    0
   1    0
   0
   0    1    0    2  
 0    1
   0    1    0
   1

...

(OEIS A096271 Ternary sequence which is a fixed point of the morphism 0 -> 01, 1 -> 02, 2 -> 00)

For k = 2,

S₃(2*n) =  1  
 2    1    0    1    2
   1    1    1  ...

S₃(2*n) =

(
S₃(n) + S₃(2) ) mod 3, where

S₃(2) =

For k = 3:

S₂(3*n) =  0
   1    0    2    0  
 1  ...

S₂(3*n) =

S₃(n)
=

( S₃(n)
+ 0 ) mod 3

j = 2, S_p(m) = 0,1,0,0... or p₂ = 1

A binary sequence, where the n-th element is the number of 3's in the factorization of n modulo 2.

S₂(n)

0    0    1  
 0    0
   1    0
   0
   0    0    0    1  
 0    0
   1    0    0
   0  ...

For k = 2,

S₂(2*n) =  0  
 0    1    0    0    1
   0    0    0  ...

S₂(2*n) = S₂(n) = ( S₂(n) + 0 ) mod 2

For k = 3:

S₂(3*n) =  1
   1    0    1    1  
 0  ...

S2(3*n) =

(
S₂(n) + 1 ) mod
2

j = 3, S_p(m) = 0,1,0,0... or p₂ = 1

A trinary sequence, where the n-th element is the number 3's in the factorization of n modulo 3.

S₃(n)

0    0    1  
 0    0
   1    0
   0
   2    0    0    1  
 0    0
   1    0    0
   2  ...

(OEIS A007949 mod 3)

For k = 2,

S₃(2*n) =  0  
 0    1    0    0    1
   0    0    2  ...

S₃(2*n) = S₂(n) =

( S₃(n)
+ 0 ) mod 3

For k = 3:

S₃(3*n) =  1
   1    0    1    1  
 0  ...

S₃(3*n) =

(
S₃(n) + 1 ) mod
3

j = 2, S_p(m) = 1,1,0,0... or p₁ and p₂ = 1

A binary sequence, where the n-th element is the number 2's and 3's in the factorization of n modulo 2.

S₂(n)

0    1    1  
 0    0
   0    0
   1
   0    1    0    1  
 0    1
   1    0    0
   1  ...

For k = 2,

S₂(2*n) =  1  
 0    0    1    1    1
   1    0    1  ...

S₂(2*n) =

(
S₂(n) + 1 ) mod
2

For k = 3:

S₂(3*n) =  1
   0    0    1    1  
 1  ...

S₂(3*n) =

(
S₂(n) + 1 ) mod
2

j = 2, S_p(m) = 1,1,1,1...

A binary sequence, where the n-th element is the number of all prime factors of n modulo 2.

S(n)

0    1    1  
 0    1
   0    1
   1
   0    0    1    1  
 1    0
   0    0    1
   1  ...

(OEIS A066829, A001222 modulo 2, and with the replacement 0 --> 1 and 1 --> -1 A008836, Liouville's function. )

For k = 2,

S₂

(2*n)  =  1
   0    0    1    0  
 1    0    0    1  ...

S₂

(2*n)
 =

( S₂(n) + 1 ) mod 2

For k = 3:

S₂

(3*n)
 =  1    0    0    1  
 0    1  ...

S₂

(3*n)
 =

( S₂(n) + 1 ) mod 2

For k = 4:

S₂

(4*n)
 =  0    1    1    0  ...

S₂

(4*n)

= S₂(n) = ( S₂(n) + 0 ) mod 3

All integers, S_p(m) = 1,1,1,1...

The n-th element is the number of all prime factors of n.

S(n)

0    1    1  
 2    1
   2    1
   3
   2    2    1    3  
 1    2
   2    4    1
   3  ...

(OEIS A001222, or Omega(n). The Liouville function(n) = -1^Omega(n) = A008836. Note that n is a prime when S(n) = 1.)

For k = 2,

S

(2*n)  =  1
   2    2    3    2  
 3    2    4    3  ...

S(2*n) = S(n) = S(n) + 1

For k = 3:

S(3*n)  =  1  
 2    2    3    2    3
 ...

S(3*n) = S(n) =

S(n) + 1

For k = 4:

S(4*n)  =  2  
 3    3    4  ...

S(4*n) = S(n) = S(n) + 2

Note that S(k*n) for k > 1 and n > 1 is never less than 2. These sequences "avoid" primes because k and n are always a factor of k*n which is composite.

All integers, S_p(m) = 2,3,5,7...

Letting the prime index elements of the sequence be the prime numbers in increasing order:

S_p(m) = 2
 3  5  7 ...

The sequence formed is

S(n) = 0  2  3  4
 5  5  7  6  6  7 11  7 13  9
 8  8 ...

(OEIS A001414 Integer log of n: sum of primes dividing n with repetition.)

and the nth sequence element can be expressed as

S(n) = Sum_m(

a_m*p_m ) where the prime factorization of n is
n =

p₁^a₁ * p₂^a₂^_... * p_m^a_m

This sequence modulo 2 is

S(n) mod 2 = 0 0 1 0 1 1 1 0 0 1
1 1 1 1 0 0 ...

(Not in OEIS. Is a related sequence listed, perhaps by swapping or replacement with -1? )

which is the same sequence as that formed by the prime index elements of

S_p(m)

 mod
2 = 0  1  1  1 ...

where only the first prime, 2, is even.

All integers, S_p(m) = 1,2,3,4...

Letting the prime index elements of the sequence be the positive integers in increasing order:

S_p(m)


= 1
 2  3  4 ...

The sequence formed is

S(n) = 0  1  2  2
 3  3  4  3  4  4
 5  4  6
 5  5  4 ...

(OEIS A056239. If n = product_{k >= 1} (p_k)^(c_k) where p_k is k-th prime and c_k >= 0 then a(n) = sum_{k >= 1} k*c_k.

A pseudo-logarithmic function in the sense that a(b*c) = a(b)+a(c) and so a(b^c) = c*a(b) and f(n) = k^a(n) is a multiplicative function. Essentially a function from the positive integers onto the partitions of the nonnegative integers (1->0, 2->1, 3->2, 4->1+1, 5->3, 6->1+2 etc.) so each value a(n) appears A000041(a(n)) times, first with the a(n)th prime and last with the a(n)th power of 2. Produces triangular numbers from primorials. - Henry Bottomley (se16(AT)btinternet.com), Nov 22 2001

Michael Nyvang writes (May 08 2006) that the Danish composer Karl Aage Rasmussen discovered this sequence in the 1990's: it has excellent musical properties.

This sequence modulo 2 is

S(n) mod 2 = 0 1 0 0 1 1 0 1 0 0
1 0 0 1 1 0 ...

(OEIS A080846. Fixed point of the morphism 0->010, 1->011, starting from a(1) = 0.

A cube-free word.

A generalized choral sequence c(3n+r_0)=0, c(3n+r_1)=1, c(3n+r_c)=c(n), with r_0=0, r_1=1, and r_c=2. [From Joel Reyes Noche (joel.noche(AT)up.edu.ph), Jul 09 2009]

What is the prime generating sequence for this binary sequence? It is S_p(m) mod 2 = 1 0 1 0 1 0 ...

All integers, S_p(m) = 2,1,2,1,1,2,...

Letting the prime index elements of the sequence be the number of Gaussian prime factors of the (real) prime numbers:

S_p(m)


= 2  1  2  1  1  2... (2 for prime indices
that are compound complex numbers, and 1 for Gaussian prime numbers on
the real axis)



Note that every number on the real line that is not a Gaussian prime
can be formed by a product of two complex numbers of the form (a +
bi)(a - bi) = a² + b². For example, 13 = 2²
+ 3², where 13 is the 6th prime.

The sequence formed is

S(n) = 0  2  1  4
 2  3  1  6  2  4
 1  5  2
 3  3  8 ...

(OEIS A078458. Total number of factors in a factorization of n into Gaussian primes.
Fully additive with a(p)=2 if p=2 or p mod 4=1 and a(p)=1 if p mod 4=3. - Vladeta Jovovic (vladeta(AT)eunet.rs), Jan 20 2003)

This sequence modulo 2 is

S(n) mod 2 = 0 0 1 0 0 1 1 0 0 0
1 1 0 1 1 0 ...

(OEIS A014707. a(4n)=0, a(4n+2)=1, a(2n+1)=a(n).
The regular paper-folding (or dragon curve) sequence.)Also see the morphism for this sequence.

All complex integers, S_p(m) = 1,i,-1,-i,0,0,...

S_p(m)


= 1  i  -1  -i  0  0...

The sequence formed is

S(n) = 0  1  i  2
 -1  1+i
 -i  3
 -1  0
 0  2+i
 0
 1-i  -1+i  4 ...

This sequence modulo (1+i)(1-i) is ?

All integers, S_p(m) = 1,-1,1,-1,1,-1,...

S_p(m)


= 1 -1  1 -1  1

-1

...
(periodic, zero-mean)

The sequence formed is

S(n) = 0  1  -1  2
 1  0
 -1  3
 -2  2
 1  1
 -1
 0  0  4 ...

All integers, S_p(m) = 0,1,1,2,1,2,...

S_p(m)

0 1 1 2 1 2 1 3 2 2 1 3 1 2 2 4 1 3

...
(big omega)

The sequence formed is

S(n) = 0  0  1  0
 1  1
 2  0
 2  1
 1  1
 2
 2  2  0 ...

All integers, S_p(m) = 0,1,1,0,1,0,0,1,...

S_p(m)

0 1 1 0 1 0 0 1 1 0 0 1

... (Thue-Morse
sequence)

The sequence formed is

S(n) = 0  0  1  0
 1  1
 0  0
 2  1
 1  1
 0
 0  2  0 ...

All integers, S_p(m) = 1,−1,−1,0,−1,1,−1,0,...

S_p(m)

1 -1 -1 0 -1

-1 0

... (mobius
function)

The sequence formed is

S(n) = 0  1  -1  2 -1  0
 0  3 -2
 0

-1

  1
 1
 1  -2  4 ...

All integers, S_p(m) = 0,1,3,5,3,0,...

S_p(m)

0 1 3 5 3

0

... (smallest primitive roots of primes)

The sequence formed is

S(n) = 0  0  1  0  3  1
 5  0
 2
 3

3

  1
 0
 5  4  0 ...

Morphisms with fixed points that are completely additive sequences

A large number of completely additive sequences are fixed points of morphisms -- replacement rules iteratively operating on strings.

For example, the sequence S_j(n) for j = 2 with the prime generating sequence S_p(m) = 1,0,0,0..., (or "the parity of powers of 2 in the index n" or "the number of trailing 0's in the binary representation of n"):

S₂(n)


  =  0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 0 0 1 ... ,

S_p(m)


= 1,0,0,0... or

p₁ = 1

(OEIS A096268, the period-doubling sequence, and its complement A035263)

is reproduced by the DOL system (a recursive replacement of each symbol with words composed of the same symbols, using the output of one generation as the input to the next):

0 ;

0 --> 0 1

1 --> 0 0

The first few replacements result in the strings:

0           
      (the initial symbol)

0 1

   
  (initial symbol replaced by the rule

0 --> 0 1)
0 1 0 0

(each
symbol replaced by the respective rule for each symbol

)
0 1 0 0 0 1 0 1 (...)

...

and the system evolves to be identical with S₂(n), where S_p(m)


= 1,0,0,0...

. or

p₁
= 1

Which sequences S_j(n) can be produced by such a replacement system? I don't know. Below is a list of many that do. Note that all prime generated sequences, which form a basis for all k-similar sequences, are represented by a morphism.

All of the binary sequences (j = 2) with a single prime set member are produced by this sequence of morphisms:

0; 0 ->       0
1

j
= 2,

S_p(m)


= 1,0,0,0... or

S₂(n|p₁=1)

   1 ->       0 0

(OEIS A096268 the period-doubling sequence, (A035263 + 1) mod 2, A007814 mod 2, (A001511 + 1) mod 2)

0; 0 ->     0 0
1

j
= 2,

S_p(m)


= 0,1,0,0... or

S₂(n|p₂=1)
1 -> 0 0 0

0; 0 -> 0 0 0 0 1

j = 2, S_p(m)


= 0,0,1,0...

or S₂(n|p₃=1)

1 -> 0 0 0 0 0

... ...

0; 0 -> 0^p_m

^-1
1

j = 2, S_p(m)


= 0,0,...1,0,0...

or S₂(n|p_m=1)
1 -> 0^p_m , where 0^p_mindicates the word of p_m0's, 0₁ 0₂ 0₃ ... 0_pm

All natural number sequences with a single prime set member are produced by this sequence of morphisms with an unbounded number of related rules:

( 0; 0-> 0 1 All integers, S_p(m)


= 1,0,0,0...

or S(n|p₁=1)
1 -> 0 2 2 -> 0 3 3 -> 0 4 ... ... )

The fixed point is OEIS A007814 the binary carry sequence, the ruler function A001511 - 1, or the greatest k such that 2^k divides n, or 2-adic valuation of n. A007814 mod 2 and A001511 mod 2 are the period-doubling sequences A096268 and A035263 respectively:

( 0; 0-> 0 0 1 All integers, S_p(m)

0,1,0,0... or S(n|p₂=1)
1 -> 0 0 2
2 ->0 0 3
3 ->0 0 4
... ... )

The fixed point is OEIS A007949, or the greatest k such that 3^k divides n, or the 3-adic valuation of n.

( 0; 0 -> 0^m-11 All integers, S_p(m)

0,0,...1,0,0... or S(n|p_m=1)
1 -> 0^m-12
2 -> 0^m-13
3 -> 0^m-14
... ... ), where 0^m-1 indicates the word of (m-1) 0's, 0₁ 0₂ 0₃ ... 0_m-1

The fixed points are identical to the m-adic valuations of n:

Any j with any single prime set member S(p_m) = 1 are produced by this sequence of morphisms:

This generalizes the morphisms above to all j.

( 0; 0 -> 0^m-1 1 j, S_p(m)

0,0,...1,0,0... or S_j(n|p_m=1)
1 -> 0^m-12
2 -> 0^m-13
... ...
j -> 0^m-1 0 ), where 0^m-1 indicates the word of (m-1) 0's, 0₁ 0₂ 0₃ ... 0_m-1

For example, j = 3 and m = 2:

0; 0 -> 0 1

j
= 3,

S_p(m)


= 1,0,0,0...

or S₃(n|p₂=1)

   1 -> 0 2

        2
-> 0 0

The fixed point is OEIS A096271, Recurrence: a(2n) = 0, a(2n+1) = (a(n)+1) mod 3

Other morphisms that result in a k-similar sequence:

0; 0 -> 0 1 1

j =
2,

S_p(m) = 1,1,1,0,1,0,1,0,1,1,0,0,1,0,1,1...

   1 -> 0 1 0

S_p(m)


= 1 for p_m

{2,3,5,11,17,23,29,41,47,53,59,71,83...}

(p_mappears to be A045309, primes congruent to 2 mod 3, and 3 itself.)

The fixed point is OEIS A156595 ("This sequence draws the Sierpinski gasket, when iterating he following odd-even drawing rule : If "1" then draw a segment forward, if "0" then draw a segment forward and turn 120A degs right if in odd position or left if in even position."):

(
0; 0 -> 0
2

j = 2, S_p(m) = 1,1,1,0,1,0,1,0,1,1,0,0,1,0,1,1...

     1 -> 0
3

S_p(m)


= 1 for p_m

{3,7,11,19,23,31,43,47,59,67,71,79,83...}

2 -> 1 2

     3 -> 1 3 )
mod 2

(p_mappears to be A002145, primes congruent to 3 mod 4. Also the prime numbers that are also Gaussian primes.)

The paper-folding, or dragon curve, sequence OEIS A014707, and (A014577 + 1) mod 2.

( 0; 0 -> 0 1 0

j = 2, S_p(m)

0,1,1,0,1,0,1...

       
  1 -> 0 1 1 )
mod 2

S_p(m) = 1

for

p_m = {2,5,11,17,...}

(p_m are odd index primes of the ordered prime set. A031368 Primes p(2n-1). )

S(n) = 0 1 0 0 1 1 0 1 0 0 1 0 0
1 1 0 ...

OEIS A080846. Fixed point of the morphism 0->010, 1->011, starting from a(1) = 0.
Note that this morphism is the same as OEIS A156595 above, but the rules are swapped.

A cube-free word.A generalized choral sequence c(3n+r_0)=0, c(3n+r_1)=1, c(3n+r_c)=c(n), with r_0=0, r_1=1, and r_c=2. [From Joel Reyes Noche (joel.noche(AT)up.edu.ph), Jul 09 2009]

Can these morphisms be generalized, to prime generated sequences where p include primes congruent to n mod (n-1)?

[ To Do: This is called the paper-folding sequence because it is reproduced by the ordered fold directions in paper that is repeatedly folded (each fold operation interleaves a new set of fold directions). It is called the dragon curve sequence because a turtle graphics (finite state) machine operating on the sequence results in the self-similar fractal tile called the dragon curve. Manfred Schroeder, in "Fractals, Chaos, Power Laws" (1991) summarizes these relationships, and shows that the dragon curve has self-similar points that lie on logarithmic spirals. It seems to me that this is a direct result of k-similarity. Every k-similar sequence should have some turtle graphics representation with an infinite set of embedded logarithmic spirals. Are they all the dragon curve, or relatives of the dragon curve?

Try Liouville's function, j = 2, p = {all primes}, with the dragon curve's transducer.]

Which other completely additive sequences are fixed points of morphisms? How do you find morphisms that result in completely additive sequences? What is the relationship between the morphism and the prime generating sequence Sp(m)?

Coprime generation of additive sequences

Sequences formed by the same construction process but with a generating sequence that contains only pairwise coprime elements (and 0 elsewhere) also include arithmetic self-similarites, but not as many (i.e. not for every k). Sequences generated this way are additive, in that S(a*b) = S(a) + S(b) when a and b are coprime. This is the same as additive functions if the sequence is considered as operating on the integer indices. An additive sequence S_j is formed when:

The n-th element S_j(n)
is the number of
times a number in the sequence S_cp(m)
= cp₁,
cp₂,
..., where indices of non-zero elements are pairwise coprime,

is
a factor of
the index n

, times cp_n

,
modulo j.

then

S_j(k*n)

 = (
S_j(n)
+ S_j(k) ) mod j  iff k is 1,

S_cp

(k)
> 0, or k is
pairwise coprime with all

S_cp

(k)
> 0

For example, with j = 2 and

S_cp(m)

= 0,0,0,1,0,...:

S₂(n)


  =  0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 ...

and the numbers k for which this is self-similar

S₂(k*n) = S₂

(n)
+ S

₂

(k) iff k is 1, 4,
or is coprime to 4

are 1, 4, and all odd numbers.

I don't know how to prove this yet, but the proof will be similar to the proof for the prime generated sequences. If it's true, the prime generated sequences can be viewed as a special subset of these coprime generated sequences.

[To Do: Morphisms with fixed points that are coprime generated sequences.]

Proofs

Prime generated sequences are completely additive

Prove that the j, p{p1,p2,..) construction of S(n) satisfies

S_j(k*n)

 = (
S_j(n) + S_j(k) ) mod j

for every k.

First consider the case of sequences on all natural numbers (including 0). The sequence S(n) is the number of not necessarily distinct prime factors of n that are in the set p = {p₁,p₂,...p_i}, where each p_i is a unique prime.

Let fn and fk be the set of all not necessarily distinct factors of n and k, and fnk be the set of all factors of nk.
n is the product P(fn) and k*n is the product P(fkn), and P(fkn) = P(fn)*P(fk).
Let #(fn) be the number of not necessarily distinct factors in the set fn. Then

#(fkn)    = #(fn)
  + #(fk)

For every unique prime factor member p_i of the sets f:

#(fkn|p_i) = #(fn|p_i

)
+ #(fk

|p_i

), because every number
has a unique set of prime factors

So for all members of set of primes p (adding the above for all p_i in p)

#(fkn|p)


 = #(fn

|p) + #(fk|p)


for all n and any set of primes p

Therefore

S(k*n)

  
 =   S(n)  + S(k)

for all n and any set of primes p.

If we take each side and each term modulo j:

#(fkn|p) mod j

  = (
#(fn

|p) mod j + #(fk|p

)
mod j

) mod j,

 for all n
and any set of primes p

S_j(k*n) = ( S_j(n) + S_j(k) ) mod j

for all j, k, n and any set of primes p.

Construction of all completely additive sequences

Which sequences S(n) satisfy

S'(k*n)

 = (
S'(n) + c'_k ) mod j

for all k?

Let

S'(n)

 = S(n)
+

S'(1)

so that

S(1) = 0

and find all sequences S(n)such that:

S(k*n)

 = S(n) +
c_k

The c_k's satisfy

S(k*1)

 = S(1)
+ c_k

c_k = S(k)

S(k*n) = S(n) +

S(k)

So for any positive integers

a > 0

b > 0

S(a*b)

 =
S(a) +

S(b)

Every sequence that satisfies this relationship, and sequences with the element wise addition of any arbitrary constant S'(1), satisfies

S'(k*n)

 = (
S'(n) + c'_k ) mod j

Note that a*b is a composite integer, although a or b are not necessarily composite. This leaves only the values at all prime indices, p_m, undetermined: values at non-prime indices can be evaluated as unique composites (additions) of values at prime indices.

The elements of the sequence S at only sequential prime indices p_m are

S_p(m)


= S(

p_m)


= S(2)
 S(3)  S(5) ...

For every possible S_p(m)-- any infinite sequence -- these prime index elements are sufficient to uniquely find every element of a k-similar sequence by repeated application of

S(a*b)

 = S(a)
+

S(b)

because every sequence element, at any index n, can be found using the unique prime factorization of n:

S(p₁^q*p₂^r*p₃^s...

) = q*S(p₁)
+

r*S(p₂)

s*S(p₃) ...

Note that there are no restrictions on the values of S_p(m) = S(p_m). They can be positive or negative integers, or real values. In fact they can be any object for which addition is defined -- any additive group.

"There are many things that can be added: numbers, vectors, matrices, spaces, shapes, sets, functions, equations, strings, chains..." Alexander Bogomolny

These sequences modulo j also satisfy

S(k*n)

 = S(n)
+

S(k)

which amounts to forming the sequences with the generating primes

S_p(m)

 mod
j

[To Do: Finish this proof.]

All such integer sequences can be formed as linear combinations of completely additive sequences for which the element at a single prime index is 1, and at all other prime indices is 0.

S(n)
= a2*S₂

(n)

a3*S₃(n) + a5*S₅(n)...

S(p_m)

 =
1 for a single m, p_m prime

= 0

for
all other m, p_m

 prime

[To Do: Show that every sequence includes all integers, and that for every j the sequences are unique.]

[To Do: Informal proofs:

Prove that all

( 0; 0 -> 0^m-1 1 j, S_p(m)


= 1 and

S_p(n n.e. m) = 0
1 -> 0^m-12
2 -> 0^m-13
... ...
j -> 0^m-1 0 )

and are those sequences contructed by j, S_p(m)= 1 andS_p(n n.e. m) = 0, so they satisfy

S_j(k*n)

 = (
S_j(n) + S_j(k) ) mod j

S_j(n) p = {pa, pb} + S_j(n) p = {pa, pc} = S_j(n) p = {pb, pc}

]

Other arithmetic subsequences of completely additive sequences

The properties of the subsequences S(kn) are outlined above. But what about arithmetic subsequences S(kn-c), with c = [1,k-1]?

These subsequences are also the fixed point of morphisms, with rules that are compounds (c>k/2) or mirrored compounds (c<k/2) of the sequence's morphism rules. For example, the Period-doubling sequence:

PD(n), (j = 2, p = {2})

0; 0 -> 0 1

1 -> 0 0

has subsequences:



PD(2*n-1) = 0 =   (the trivial sequence of all zeros, or (j =
2,

S_p(m) = 0,0,0 ...

0; 0 -> 0 0



PD(3*n-2) =

0; 0 -> 0 0 0 1

   1 -> 0 1  0
1

PD(3*n-1) =

1; 0 -> 1 0  0 0
   OR  the complement of

0; 0 -> 0
1  1 1

        1
-> 1 0  1 0

   1
-> 0 1  0 1





PD(4*n-c)

= PD(

2*n) for even c

          = 0 or 1  trivial sequences for
odd c

PD(5*n-4) =

0; 0 -> 0 1 0 0  0 1 0 0
 0 1 0 1  0 1 0 0

1 -> 0 1 0 1


0 1 0 0  0 1 0 1  0 1 0 0

Also,



PD( k₂*(k₁*n-c) ) =

PD( k₁

*n-c
)   for parity of 2's in

k₂

's
factors even

inv(
PD(

k₁

*n-c
) )

for parity of 2's in k₂

's
factors

odd

even though these sequences are not PD itself or a simple shift. (But the Klop group assures me "that Sebastian Stern, who was a master student in our department, has shown that all arithmetic subsequences of M [the Thue-Morse sequence] can be transduced back to M. This supports the primality conjecture that we have: all FST-reducts of M are either periodic or FST-equivalent to M.")

This is clear from using the prime generating sequence S_p(m) = 1,0,0 ..., which results in S(2) = 1; k₂ multiplies the index (k₁*n-c) and so changes the number of 2's in the indices factorization by the number of 2's in k₂'s factorization. For example, with:

k₂ = 5, k₁ = 3, c = 2;

PD( n' = 5, 20, 7, 10, ...) = PD( n' = 1, 4, 7, 10, ... )

we see that the parity 2's in the factors of the indices is unchanged by multiplication with the odd number 5.

The differences of these arithmetic subsequences are interesting too. For example the difference matices for PD(3*n-2) and PD(3*n-1)are similar to that of the sequence itself, but with a scaling factor of 4 rather than 2 -- the top 1/4 x 1/4 of the matrices are self-similar to the full matrix.


diff matrix of PD(3*n-2)	diff matrix of PD(3*n-1)

Miscellaneous

[To Do (on new page):

A008836, Liouville's function, L, results in an interesting sequence: Sum_1_to_n( 2^nL₀ - 2^nL₁ ) = 1, 1, 1, 3, 5, 11, 21, 41, 83, 277, 553, 1105 ...

Check that these are correct, and relate to Sum_n( L_-1 - L₁ )

(Non)Automaticity of Number Theoretic Functions
Michael Coons

]

[To Do: What are "diff" and "undiff" (or "sum") series for some of these?

undiff( S(n)

 ) 
 =

 [0]   1    2
 
 3    3    3    3    4
   5    4    3    4  
 4    3    4    6    5
   4  ...

S(n)

0    1  
 1  
 2    1    2    1    3
   2    2    1    3  
 1    2    2    4    1
   3  ...

(OEIS A001222)

diff( S(n)

)  
 =

1    0    1  
-1    1   -1    2   -1
   0   -1    2   -2  
 1    0    2   -3    2  ...

(OEIS A076191)

diff²( S(n)

)  
=

-1 1 -2 2


  -2    3   -3    1
  -1     ...

=


 2   -3    4

-4


   5   -6    4   -2
  -1     ...

=

 -5
   7   -8

9


 -11   10   -6    1    ...

= 12 -15 17 -20


  21  -16    7    ...

It would be nice to see the diagrams for these. What is the left column complement for this sequence? 0 1 -1 0 2 -5 12 ...

S(n)

0  
 1  
 1  
 2    1    2    2    3
   1    2    2    3  
 2    3    3    4    1
   2  ...

(A000120

1's-counting sequence: number of 1's in binary expansion of n. )

diff( S(n)

)  
 =

1    0    1  
-1    1    0    1   -2
   1    0    1   -1  
 1    0    1   -3    1  ...

(A088705)

diff²( S(n)

)  
=

-1 1 -2 2


  -1    1   -3    3
  -1     ...

]

[To Do (on a new page): Emergence is the way patterns arise out of a multiplicity of relatively simple interactions. This example of emergence, of self-similar patterns in the fixed points of simple (short) morphisms, is appealing to me as a prototypical, a well defined primitive.

From Emergence in mathematics:

"Although the above examples of emergence are often contentious, mathematics provides a rigorous basis for defining and demonstrating emergence. In Emergence is coupled to scope, not level, Alex Ryan shows that a Möbius strip has emergent properties (Ryan 2006). The Möbius strip is a one-sided, one-edged surface. Further, a Möbius strip can be constructed from a set of two-sided, three edged, triangular surfaces. Only the complete set of triangles is one-sided and one-edged: any subset does not share these properties. Therefore, the emergent property can be said to emerge precisely when the final piece of the Möbius strip is put in place. An emergent property is a spatially or temporally extended feature – it is coupled to a definite scope, and cannot be found in any component because the components are associated with a narrower scope."

The Ryan paper is interesting. The Möbius strip example is a good toy system, but these self-similar sequences are a better example of scope. The paper also makes a nice point about how emergence is limited in such formal systems.]

References

Analytic Number Theory (page 9)

Henryk Iwaniec
Emmanuel Kowalski
(also see Primes in Arithmetic Progressions chapter)

On Sets Characterizing Additive Arithmetical Functions

Kark-Heinz Indlekofer

"...we investigate some properties of additive and completely additive arithmetical functions. An additive function is uniquely determined by its values on prime powers ... whereas a completely additive function is already determined by its values on the set of primes."

Janko Bračič, Kolobar aritmetičnih funkcij (Ring of arithmetical functions), (Obzornik mat, fiz. 49 (2002) 4, pp. 97–108)

Functional Analysis and Additive Arithmetic Functions
P.D.T.A. Elliott

"A function is arithmetic if it is defined on the positive integers. Those arithmetic functions which assume real values and satisfy f(ab) = f(a) + f(b) for mutually prime integers a, b are classically called additive. The following examples illustrate the interest of these functions, both for themselves and for their applications.
An additive function is defined by its values on the prime powers. ..."

------------------------------------
Comments are welcome (dow[at]uoregon.edu).