An extension of the Jacobi symbol.

[Peter Luschny]

The Kronecker Symbol, here written as (n|m), is defined as
an extension of the Jacobi symbol to cover the case m is even
or negative. It has two additional rules for m=2 and m=-1.

http://mathworld.wolfram.com/KroneckerSymbol.html

On mathworld there are also links to various related sequences
on OEIS.

Recently I implemented the Jacobi symbol with Sage. Testing
the implementation I realized that it works out of the box
for all n,m integers. Thus it looks like a natural extension
of the Jacobi symbol. However, it behaves very different from
the KroneckerSymbol.

-----------------------------------------------------------------
print [Jacobi(0, -n) for n in (-10..10)]
print [Jacobi(n,2*n) for n in (-10..10)]
print [Jacobi(-n,-n) for n in (-10..10)]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0]
[0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, -1, 1, 0, 1, 0, 0, 0, 1, 0, 0]
-----------------------------------------------------------------
print [kronecker_symbol(0, -n) for n in (-10..10)]
print [kronecker_symbol(n,2*n) for n in (-10..10)]
print [kronecker_symbol(-n,-n) for n in (-10..10)]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
-----------------------------------------------------------------
print [Jacobi(-6,n) for n in (-10..10)]
print [kronecker_symbol(-6,n) for n in (-10..10)]
[-1, 0, 1, -1, 0, -1, -1, 0, 1, -1, 0, 1, -1, 0, 1, 1, 0, 1, -1, 0, 1]
[ 0, 0, 0, -1, 0, -1, 0, 0, 0, -1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0]
----------------------------------------------------------------------

Who sees the pattern? Who sees the meaning?
Cheers, Peter

def Jacobi(a, n) :
r = 1
while a <> 0 :
if a < 0 :
a = -a
if mod(n, 4) == -1 : r = -r
while is_even(a) :
a = a / 2
m = mod(n, 8)
if m == 3 or m == -3 : r = -r
ma = mod(a, 4); mn = mod(n, 4)
if ma == -1 and mn == -1 : r = -r
t = a; a = n - a * ceil(n/a - 1/2); n = t

return 0 if n > 1 else r

[Peter Luschny]

For illustration: looking up the Jacobi symbol on Wikipedia

http://en.wikipedia.org/wiki/Jacobi_symbol#Using_the_Jacobi_symbol

there is an example of its computation which takes 14 steps.
For comparison, tracing the algorithm above shows only 7 steps.

( a, n, r)
----------------
(1001, 9907, 1)
(-103, 1001, 1)
( -29, 103, 1)
( -13, 29, -1)
( 3, 13, -1)
( 1, 3, -1)
( 0, 1, -1)
return -1

[seqcomp]

From Antti Karttunen:

 

Please could you indent above definition so, that one can grasp it better?

C- and Scheme-code below from my old source.

If Jacobi-symbol were naturally extended to all natural numbers, not just odd ones, then one might compute many of the "Jacobi-sequences" I computed

for the odd numbers:

http://oeis.org/search?q=author%3Akarttunen+jacobi&language=english&go=Search

 Here's our C-version. The teaching: Never implement mathematician's
 or logician's elegant formulae directly, without thinking!
 Working in GF(2) with XOR & AND is much more natural for
 computers than working in isomorphic multiplicative group of {+1, -1}
 with MUL.
 We also convert the recursion in our formula to a simple loop.
 q should be always odd!

 int js_ULI(ULI p,ULI q)
 {
     int s = 0; /* 0 in bit-1 stands for +1, 1 in bit-1 for -1. */
     ULI new_p;
 loop:
     if(0 == p) { return(p); }
     if(1 == p) { return(1-(s&2)); } /* Convert 1 in bit-1 to -1, 0 to +1. */
 
     if(p&1) /* We have an odd p. */
      {
 /* If both p & q are 3 mod 4, then sign changes, otherwise stays same: */
        s ^= (p&q); /* Only the bit-1 is significant, others are ignored. */
        new_p = q % p; /* Could we have a simple - here as with Euclid? */
        q = p;
        p = new_p;
        goto loop;
      }
     else /* We have an even p. So (2k/q) = (2/q)*(k/q) */
      {   /* where (2/q) = 1 if q is +-1 mod 8 and -1 if q is +-3 mod 8. */
          /* I.e. sign changes only if q's lower bits are (011) or (101),
             i.e. if the bit-1 and bit-2 xored yield 1. */
        s ^= (q^(q>>1));         /* Thus, this does it. */
        p >>= 1;
        goto loop;
      }
 }

And Scheme-version:

(define (fix:jacobi-symbol p q)
 (if (not (and (fix:fixnum? p) (fix:fixnum? q) (fix:= 1 (fix:and q 1))))
     (error
       "fix:jacobi-symbol: args must be fixnums, and 2. arg should be odd: "
            p q
     )
     (let loop ((p p)
                (q q)
                (s 0))  ;; 0 in bit-1 stands for +1, 1 in bit-1 for -1.
       (cond ((fix:zero? p) 0)
             ((fix:= 1 p) (fix:- 1 (fix:and s 2)))
             ((fix:= 1 (fix:and p 1)) ;; Odd p ?
                (loop (fix:remainder q p) p (fix:xor s (fix:and p q)))
             )
             (else ;; It's even, get rid of one 2:
                (loop (fix:lsh p -1) q (fix:xor s (fix:xor q (fix:lsh q -1))))
             )
       )
     )
 )
)

[Peter Luschny]

AK> "Please could you indent above definition so, that one can 

grasp it better?"

    

This is a problem with the new design of the Google groups.

In the old groups you could change the display to fixed width

fonts and everything was all right. This option is gone as far 

as I see. Now you are forced to format the text. This is not 

nice. In particular how can the old posts which rely on fixed

width fonts ever be read properly?

AK> "C- and Scheme-code below from my old source."

Thanks for the cute implementations!

AK> "If Jacobi-symbol were naturally extended to all natural numbers,

not just odd ones..."

Well, but this is what Kronecker did. People seem to be happy

with his extension. Are you not?

AK> ".. then one might compute many of the "Jacobi-sequences" 

I computed for the odd numbers.."  

Is there a sequence which would profit from this in particular?

[Peter Luschny]

AK> "Please could you indent above definition so, that one can 

grasp it better?"

Yes. Here it comes, ExtendedJacobi. And I have ported your 

C-program to Sage. And Joerg Arndt's implementation of Cohen's

algorithm. So now we have three candidates.

============================================================

def ExtendedJacobi(a, n) : 

    r = 1 

    while a <> 0 : 

        if a < 0 : 

            a = -a 

            if mod(n, 4) == -1 : r = -r 

        while is_even(a) : 

            a = a / 2 

            m = mod(n, 8) 

            if m == 3 or m == -3 : r = -r 

        ma = mod(a, 4); mn = mod(n, 4) 

        if ma == -1 and mn == -1 : r = -r 

        t = a; a = n - a * ceil(n/a - 1/2); n = t 

    return 0 if n > 1 else r 

============================================================

def Standard(p, q) : # Folklore algorithm, ported from Antti Karttunen's C implementation.

    s = 0; # 0 in bit-1 stands for +1, 1 in bit-1 for -1. 

    xor = lambda x, y: x.__xor__(y) 

    while true :

        if 0 == p : return p

        if 1 == p : return 1 - (s&2) # Convert 1 in bit-1 to -1, 0 to +1. 

        

        if 1 == p&1 : # We have an odd p. 

            #If both p & q are 3 mod 4, then sign changes, otherwise stays same: 

            s = xor(s,p&q)  # Only the bit-1 is significant, others are ignored. 

            new_p = q % p # Could we have a simple - here as with Euclid? 

            q = p; p = new_p

        else : # We have an even p. So (2k/q) = (2/q)*(k/q) 

            # where (2/q) = 1 if q is +-1 mod 8 and -1 if q is +-3 mod 8. 

            # I.e. sign changes only if q's lower bits are (011) or (101),

            # i.e. if the bit-1 and bit-2 xored yield 1. 

            s = xor(s,xor(q,q>>1))  # Thus, this does it. 

            p >>= 1

            

============================================================

def Cohen(a, b) : # Algorithm from Cohen, ported from Jörg Arndt's C implementation.

    # tab2[ a & 7 ] := (-1)^((a^2-1)/8)

    tab2 = [0, 1, 0, -1, 0, -1, 0, 1] 

    if 0 == b: return int(1 == a)

    if 0 == (a|b)&1 : return 0

    v = 0

    while is_even(b): v += 1; b >>= 1 

    k = 1 if is_even(v) else tab2[ a & 7 ]

    

    while true :

        if 0 == a: return 0 if b>1 else k 

        v = 0

        while is_even(a): v += 1; a >>= 1 

        if is_odd(v): k *= tab2[ b & 7 ]  # k *= (-1)**((b*b-1)/8)

        if a & b & 2 : k = -k        # k = k*(-1)**((a-1)*(b-1)/4)

        r = a; a = b % r; b = r

           

[Antti Karttunen]

maanantai, 6. elokuuta 2012 12.14.45 UTC+3 Peter Luschny kirjoitti:

AK> "Please could you indent above definition so, that one can 

grasp it better?"

    

This is a problem with the new design of the Google groups.

In the old groups you could change the display to fixed width

fonts and everything was all right. This option is gone as far 

as I see. Now you are forced to format the text. This is not 

nice. In particular how can the old posts which rely on fixed

width fonts ever be read properly?

AK> "C- and Scheme-code below from my old source."

Thanks for the cute implementations!

AK> "If Jacobi-symbol were naturally extended to all natural numbers,

not just odd ones..."

Well, but this is what Kronecker did. People seem to be happy

with his extension. Are you not?

I don't know, I haven't tested it yet. See below.

 

AK> ".. then one might compute many of the "Jacobi-sequences" 

I computed for the odd numbers.."  

Is there a sequence which would profit from this in particular?

Same thing here, I don't know, as I haven't tried. And in any case, most of my sequences are just

shots into the dark. In this case, the existing "Jacobi"-sequences I computed

for odd numbers would be bisections of new sequences computed with either Kronecker or

some other version of "ExtendedJacobi" for all natural numbers.

Yours,

Antti Karttunen

(And sorry for not responding here earlier. Now it also seems that the font is OK, that is,

fixed width.)

[Antti Karttunen]

tiistai, 7. elokuuta 2012 3.42.37 UTC+3 Antti Karttunen kirjoitti:

maanantai, 6. elokuuta 2012 12.14.45 UTC+3 Peter Luschny kirjoitti:

AK> "If Jacobi-symbol were naturally extended to all natural numbers,

not just odd ones..."

Well, but this is what Kronecker did. People seem to be happy

with his extension. Are you not?

I don't know, I haven't tested it yet. See below.

Okay, now I start dimly recalling what was my motivation (with those "Jacobi" sequences).

I think the important feature in my case is that the "extended Jacobi symbol" (Here "EJ",

whether it is Kronecker symbol, or some new variant) would return for EJ(i,n) with i ranging from 1 to n,

the equal number of times both +1 and -1, plus possibly some zeros.

(Okay, now I remember that this condition already fails even with ordinary Jacobi symbol when

n is an odd square. But if it doesn't fail for too many of even n, then good.)

Then it might make sense to compute analogues of the following sequences (for all natural numbers):

http://oeis.org/A112046 

http://oeis.org/A166100

http://oeis.org/A166089

http://oeis.org/A166409 

Maybe also: http://oeis.org/A095100 

(But probably not much more sense than there originally was... ;-)

Yours,

Antti

[Peter Luschny]

> I think the important feature in my case is that the "extended Jacobi
> symbol" (Here "EJ",
> whether it is Kronecker symbol, or some new variant) would return
> for EJ(i,n) with i ranging from 1 to n,
> the equal number of times both +1 and -1, plus possibly some zeros.

I saw yours A054431 which is a nice symmetric variant of A054521
which is the unsigned variant of A215200.

http://oeis.org/search?q=id%3AA054521%7Cid%3AA054431%7Cid%3AA215200&sort=&language=&go=Search

I like this triangle as the row sums give the Euler totient function.

On the other hand the row sums of the corresponding signed (Kronecker)
triangle is not in OEIS but might deserve also some study. Perhaps
I should add this sequence.

Euler totient:
1,1,2,2,4,2,6,4,6,4,10,4,12,6,8,8,16,6,18,8,12,...
signed Euler totient: 1,1,2,2,0,2,2,0,6,2, 6,0, 2,4,4,8, 4,0, 8,0,
0,...

This in turn leads to the interesting question for which n the "signed
Euler
totient function" vanishes:

5, 8, 12, 18, 20, 21, 24, 28, 32, 40, 44, 48, 52, 53, 56,...

[Peter Luschny]

I will show in this post three examples comparing the performance

of the three algorithms given above

* EJ = ExtendedJacobi

* Antti

* Cohen

I have slightly tuned EJ by inserting as a preparation step

the reduction of n to an odd value, exactly as it is done in

Cohen's algorithm, i.e. by inserting

if is_even(n) :

   v = 0 

   while is_even(n): v += 1; n = n/2 

   r = 1 if is_even(v) else [0,1,0,-1,0,-1,0,1][a&7]

   if debug: loops += 1; print(a,n,r,loops)

   

before the while-loop.   

How to read the output: (a, b, (a|b), step)

   

The first example is from Wikipedia.

====================================

http://en.wikipedia.org/wiki/Jacobi_symbol#Using_the_Jacobi_symbol

Antti: 9 steps 

---------------

   (1001, 9907, 0, 0)

   (898, 1001, 1, 1)

   (449, 1001, 1, 2)

   (103, 449, 1, 3)

   (37, 103, 1, 4)

   (29, 37, 1, 5)

   (8, 29, 1, 6)

   (4, 29, -1, 7)

   (2, 29, 1, 8)

   (1, 29, -1, 9)

Cohen: 6 steps

---------------- 

   (1001, 9907, 0, 0)

   (898, 1001, 1, 1)

   (103, 449, 1, 2)

   (37, 103, 1, 3)

   (29, 37, 1, 4)

   (8, 29, 1, 5)

   (0, 1, -1, 6)

    

EJ: 6 steps

---------------- 

   (1001, 9907, 0, 0)

   (-103, 1001, 1, 1)

   (-29, 103, 1, 2)

   (-13, 29, -1, 3)

   (3, 13, -1, 4)

   (1, 3, -1, 5)

   (0, 1, -1, 6)

The second example:

==================  

Antti: 18 steps 

---------------

   (109981, 737777, 0, 0)

   (77891, 109981, 1, 1)

   (32090, 77891, 1, 2)

   (16045, 77891, -1, 3)

   (13711, 16045, -1, 4)

   (2334, 13711, -1, 5)

   (1167, 13711, -1, 6)

   (874, 1167, 1, 7)

   (437, 1167, 1, 8)

   (293, 437, 1, 9)

   (144, 293, 1, 10)

   (72, 293, -1, 11)

   (36, 293, 1, 12)

   (18, 293, -1, 13)

   (9, 293, 1, 14)

   (5, 9, 1, 15)

   (4, 5, 1, 16)

   (2, 5, -1, 17)

   (1, 5, 1, 18)

Cohen: 10 steps

----------------

   (109981, 737777, 0, 0)

   (77891, 109981, 1, 1)

   (32090, 77891, 1, 2)

   (13711, 16045, -1, 3)

   (2334, 13711, -1, 4)

   (874, 1167, 1, 5)

   (293, 437, 1, 6)

   (144, 293, 1, 7)

   (5, 9, 1, 8)

   (4, 5, 1, 9)

   (0, 1, 1, 10)

EJ: 6 steps

---------------- 

   (109981, 737777, 0, 0)

   (-32090, 109981, 1, 1)

   (-2334, 16045, -1, 2)

   (-293, 1167, 1, 3)

   (-5, 293, -1, 4)

   (-2, 5, -1, 5)

   (0, 1, 1, 6)

The third example:

================== 

Here the second parameter is even but Antti's prog is not

prepared to handle this case. 

Cohen: 12 steps

----------------

   (737779, 121080, 0, 0)

   (737779, 15135, -1, 1)

   (15135, 737779, 1, 2)

   (11299, 15135, -1, 3)

   (3836, 11299, 1, 4)

   (750, 959, -1, 5)

   (209, 375, 1, 6)

   (166, 209, 1, 7)

   (43, 83, 1, 8)

   (40, 43, -1, 9)

   (3, 5, 1, 10)

   (2, 3, 1, 11)

   (0, 1, -1, 12)

EJ: 8 steps

----------------

   (737779, 121080, 0, 0)

   (737779, 15135, -1, 1)

   (15135, 737779, 1, 2)

   (-3836, 15135, -1, 3)

   (-209, 959, -1, 4)

   (-86, 209, 1, 5)

   (-6, 43, 1, 6)

   (1, 3, -1, 7)

   (0, 1, -1, 8)

With some very rare exceptions EJ's performance is better or

equal to the Cohen's algorithm.

[Peter Luschny]

>> I think the important feature in my case is that the 

>> "extended Jacobi symbol" ... would return for EJ(i,n) with

>> i ranging from 1 to n, the equal number of times both +1 

>> and -1, plus possibly some zeros.

 

>Euler totient:        1,1,2,2,4,2,6,4,6,4,10,4,12,6,8,8,...

>signed Euler totient: 1,1,2,2,0,2,2,0,6,2, 6,0, 2,4,4,8,,...

... now A215283

>This in turn leads to the interesting question for which n 

>the "signed Euler totient function" vanishes:

>5, 8, 12, 18, 20, 21, 24, 28, 32, 40, 44, 48, 52, 53, 56,...

... now A215284

Today the editors of OEIS are quick :-)

But nowadays they are much more stingy with the predicate 'nice'.

Not even for the 'signed Euler totient function' ;-))

[Antti Karttunen]

tiistai, 7. elokuuta 2012 16.15.38 UTC+3 Peter Luschny kirjoitti:

I will show in this post three examples comparing the performance

of the three algorithms given above

* EJ = ExtendedJacobi

* Antti

* Cohen

I have slightly tuned EJ by inserting as a preparation step

the reduction of n to an odd value, exactly as it is done in

Cohen's algorithm, i.e. by inserting

if is_even(n) :

   v = 0 

   while is_even(n): v += 1; n = n/2 

   r = 1 if is_even(v) else [0,1,0,-1,0,-1,0,1][a&7]

   if debug: loops += 1; print(a,n,r,loops)

   

before the while-loop.   

Sorry, I think you are not being fair to "my" algorithm ;-), as you only count

the main iterations, but not the auxiliary iterations (of the competitors) that

get rid of the powers of 2. (as above).

What would really count as significant, is the _total count_ of operations

and the time needed to execute them. For some platforms, complete or partial

unrolling (whether manual or automatic) of the loop might improve the results, for others not.

For example, in my Bream-compiler, which compiles width-annotated subset of Scheme

to Verilog Hardware Description Language, to be executed on FPGA's,

(see: https://github.com/karttu/bream )

the ordinary Euclidean GCD-algorithm

(define (gcd a b)
   (cond ((zero? b) a)
         ((>= a b) (gcd b (- a b)))
         (else (gcd (- b a) a))
   )
)

can be also "unrolled" in such a way, that for example, two "original
iteration steps" will be "executed" in one "iteration" (cycle) of the
resulting finite state machine (a temporary syntactical kludge needed for this):

(define (gcd_once_unrolled a b)
   (let-unrolled 1 loop ((a a) (b b))
         (cond ((zero? b) a)
               ((>= a b) (loop b (- a b)))
               (else (loop (- b a) a))
         )
   )
)


Compiled to Verilog, this can be found here:

https://github.com/karttu/bream/blob/master/testprojects/t_inttests/Compiled_for_ATLYS/gcd_once_unrolled_18_18_18.v 

It depends on the other parts of the program whether the space-time trade-offs

inherent in this can be compensated elsewhere in the design.

Sorry, this probably went a bit off-topic for the sequences.

So, I am returning to that:

I forget to mention, that this sequence http://oeis.org/A095100

is an extension of http://oeis.org/A095102

the latter which has some relevance also outside of

my own sandbox-games. (See the Borwein, Choi and Coons paper).

So, could we "extend" A095100 to the other direction, 

with KroneckerSymbol?

Maybe I should test this myself.

Yours,

Antti Karttunen

[Peter Luschny]

> From George Beck:

 

> What's the definition of the signed Euler totient function?

> I seem to have missed it.

Never mind, it's brand new :-)

The Euler totient function are the row sums of 

the Euclid triangle http://oeis.org/A054521.

The signed Euler totient function are the row sums of 

the signed Euclid triangle http://oeis.org/A215200

which might also be called Kronecker's triangle. 

It is given in http://oeis.org/A215283

[Peter Luschny]

> Sorry, I think you are not being fair to "my" algorithm ;-), 

> as you only count the main iterations, but not the auxiliary 

> iterations (of the competitors) that get rid of the powers of 2.

I apologize :-) Yes I am certainly not fair from a low-level

point of view.

What I am counting are reduction steps. These are defined 

by the main while loop and end typical with a swap and a 

division r = a; a = b % r; b = r (Cohen) or new_p = q % p;  

q = p; p = new_p (Antti). I do not look at finer grained 

operations and their counts within the loop-body. (Which, 

by the way, would not make much sens using Sage in this context

as Sage has a high level approach and the mod-operations 

use Z/mZ and coercion etc., like real mathematicians do.)

> A095100 Integers whose Jacobi-vector forms a valid Motzkin-path.

Ah yes, this sounds interesting.

> Maybe I should test this myself.

Fine. I am looking forward...

[Peter Luschny]

After having looked at some of your sequences today

A095100, A095101, A095103, A166049, A166051,

I was inspired to handle the Kronecker triangle in a similar

way, thereby also demonstrating the usefulness of the Kronecker

symbol versus the Jacobi symbol in this context.

 def is_Motzkin(n):

        s = 0

        L = [kronecker_symbol(n-k, k) for k in (1..n)]

        for l in L :

            s += l

            if s < 0 : return false

        return true

These are the rows of the Kronecker triangle which are Motzkin:

[n for n in (1..100) if is_Motzkin(n)]

[1, 2, 3, 4, 6, 7, 9, 10, 11, 13, 14, 15, 16, 17, 19, 22, 25, 26, 30,

31, 34, 35, 36, 37, 39, 41, 42, 43, 46, 49, 51, 55, 58, 59, 64, 65, 66,

67, 70, 74, 78, 79, 81, 82, 85, 89, 91, 93, 94, 100]

and the complement:

[n for n in (1..100) if not is_Motzkin(n)]

[5, 8, 12, 18, 20, 21, 23, 24, 27, 28, 29, 32, 33, 38, 40, 44, 45, 47,

48, 50, 52, 53, 54, 56, 57, 60, 61, 62, 63, 68, 69, 71, 72, 73, 75, 76,

77, 80, 83, 84, 86, 87, 88, 90, 92, 95, 96, 97, 98, 99]

These are nice sequences, however I do not understand their

significance yet. Antti, can you tell us something about your

motivation behind the study of your sequences with the Jacobi

symbol?

How will the ratio Motzkin/NonMotzkin develop?

100    :   50/50

1000   :  298/702

10000  : 1999/8001 

100000 :    ?/?

[Antti Karttunen]

Well, it was not really any mathematical problem that I was trying to solve, or even shed light on,

but more of something like "artistic/experimental synthesis of different mathematical forms".

Especially I am interested when at some sector of mathematics I encounter a "form"

or pattern, that is the same or almost same as some structure at a

different field, or if there's any change that those patterns somehow 

click together. (A completely different example: http://oeis.org/A051258 )

For example, because the elementary number theory says that for all

odd primes p, the Legendre symbol L(i/p), i ranging from 1 to p-1 gets

equal number of times the value +1 and -1, then it's clear that drawing

a graph on a square grid using those values as directions (either up (=+1) or right (-1))

gives us a zig-zag graph from origo to point (p-2,p-2). Or alternatively, turning

it 45 degree clockwise and scaling (so that (+1,+1)=+1 and (+1,-1)=-1)

we get a graph from (0,0) to (p-1,0).

Then the next natural step is to ask when this path is a valid Dyck path

(a member of Catalan families), i.e. a path that never dives below the "sea level",

i.e. the X-axis.

However, I didn't start with that, but with this slightly kludgous version:

http://oeis.org/A080114 

(for drawing "Legendre's candelabras". I don't know anymore whether they

look candelabras or maybe some kind of insects?)

It was only later (next year, 2004), that I computed it with slightly different condition,

leaving out the primes 5, 13 and 37:

http://oeis.org/A095102 

and then, it was a complete surprise me, when some

of the OEIS associate editors added the link to 2008

Borwein, Choi, Coons paper, that this kind of sequence

can actually pop up in some serious mathematics!

Now, as the sequence http://oeis.org/A095100 

is computed for all odd numbers of form 4k+3

with Jacobi-symbol, which can also give zero as

its value, not just +1 or -1, it naturally changes

the combinatorial structure we should "look for" from Dyck

paths to Motzkin paths.

 

How will the ratio Motzkin/NonMotzkin develop?

100    :   50/50

1000   :  298/702

10000  : 1999/8001 

100000 :    ?/?

I would compute this also for twos powers, as I view them more natural

ranges than the powers of ten.

Yours,

Antti

 

[Antti Karttunen]

keskiviikko, 8. elokuuta 2012 19.01.20 UTC+3 Antti Karttunen kirjoitti:

...

 

For example, because the elementary number theory says that for all

odd primes p, the Legendre symbol L(i/p), i ranging from 1 to p-1 gets

equal number of times the value +1 and -1, then it's clear that drawing

a graph on a square grid using those values as directions (either up (=+1) or right (-1))

gives us a zig-zag graph from origo to point (p-2,p-2).

Of course I meant to say (p-1,p-1). Mea culpa.

A related crazy idea:

Is anyone willing to compute FFT (Fast Fourier transform) of this

graph: http://oeis.org/A165472/graph ?

This could be based instead on the variant http://oeis.org/A179416 

if that allows better application of Cooley–Tukey algorithm.

(With period 65536 instead of 65537.)

Could we get any interesting integer sequences out of the

resulting complex (?) numbers?

Yours,

Antti

[Antti Karttunen]

keskiviikko, 8. elokuuta 2012 19.26.47 UTC+3 Antti Karttunen kirjoitti:

keskiviikko, 8. elokuuta 2012 19.01.20 UTC+3 Antti Karttunen kirjoitti:

...

 

For example, because the elementary number theory says that for all

odd primes p, the Legendre symbol L(i/p), i ranging from 1 to p-1 gets

equal number of times the value +1 and -1, then it's clear that drawing

a graph on a square grid using those values as directions (either up (=+1) or right (-1))

gives us a zig-zag graph from origo to point (p-2,p-2).

Of course I meant to say (p-1,p-1). Mea culpa.

 

That is, ((p-1)/2,(p-1)/2) !

 

[Peter Luschny]

However, I didn't start with that, but with this slightly kludgous version:

http://oeis.org/A080114 

(for drawing "Legendre's candelabras". I don't know anymore whether they

look candelabras or maybe some kind of insects?)

 

[seqcomp]

[Dear George, please post in the group, not to the owner of the group.] 

From George Beck:

The attached makes me wonder if there is a way to use absolute values to get that first picture.