Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I am interested in the efficient computability of sequences.

Is it possible some ``interesting sequences'' be computed via addition formulae/semigroup operation?

Here is an artificial example.

Suppose one finds an associative operation $f : \mathbb{Z}^2 \times \mathbb{Z}^2 \to \mathbb{Z}^2$ and a sequence $a_n$ such that:

$f([a_{2n},a_{2n+1}],[a_{2m},a_{2m+1}]) = [ a_{2n+2m},a_{2n+2m+1} ]$

$f$ is associative and the result is in [$a_{2k},a_{2k+1}$] which resembles a semigroup

Let $a_n = A000069(n)$ where A000069 Odious numbers: numbers with an odd number of 1's in their binary expansion.

From the OEIS comment: $a_{2n+1} + a_{2n} = A017101(n) = 8n+3$

one can find $n,m$.

From: $a_n = \frac{1}{2} (4n + 1 + (-1)^{A000120(n)})$

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

one can find

[ $a_{2n+2m},a_{2n+2m+1}$ ]

and this seems to complete associativity and closure.

  1. So is [A000069(2n),A000069(2n+1)] $ \in \mathbb{Z}^2 $a semigroup?

  2. If yes what type of semigroup is it (the semigroup operation involves counting ones in the binary expansion)?

  3. Are there other similar examples/constructions of sequences that are not rational functions or related to multiples of points on curves (e.g. Fibonacci, Somos4).

share|improve this question
    
What does [...,...] mean? –  darij grinberg Jan 31 '11 at 11:42
    
It means the pair $( a(2n),a(2n+1))$, should I edit the post? –  joro Jan 31 '11 at 12:03
    
Ah, ok, I should have got it. But yes, editing would be good. –  darij grinberg Jan 31 '11 at 22:00

1 Answer 1

up vote 1 down vote accepted

Is your functional equation a non-vacuous constraint? Since summation is group operation, the pairs [2n,2n+1] form a group 2N, which map to your group [a(2n),a(2n+1)]. For example, for A000069

1, 2, 4, 7, 8, 11, 13, 14, 16, 19, 21, 22, 25, 26, 28, 31, 32, 35, 37, 38, 41, 42, ...
0  1  2  3  4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  
   ^  ^     ^           ^   ^           ^       ^   ^       ^           ^       ^   
----  ----  -----   -----   -----  ------  ------   -----   -----  ------  ------

each pair [2n,2n+1] is a group element is, so that we have

[a(6),a(7)] + [a(10),a(11)] = [a(16),a(17)]

and yet there seems to be no relation among a(6), a(10) and a(16).

share|improve this answer
    
@Tegiri Thank you. I wrote the example is artificial - a(n) is efficiently computable anyway. Though working with [a(2n),a(2n+1)] conceals the addition of [2n,2n+1]. –  joro Feb 1 '11 at 7:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.