Sum Over Coprime Integers = 0 (or 1)

[Michele Dondi]

NOTE: this is *not* a mistake!


On Tue, 10 Aug 2004, Leroy Quet wrote:

>> a(1) = 1;
>>
>> For each m >= 3,
>>
>> 0 = sum{1<=k<m,GCD(k,m)=1} a(k).
[snip]
> I just posted the following to the EIS, with more terms calculated
> (correctly??).
>
> %I A000001
> %S A000001 1,-1,-1,1,-1,1,1,-1,-1,1,-1,1,3,-3,-1,1,-3

I get

1, -1, -1, 1, -1, 1, 1, -1, -1, 1, -1, 1, 3, -3, -1, 1, -3, 3, 1, -1, 1, 
-1, -1, -1, 5, -1, -1, -1, -1, 1, -1, 1, -3, 5, -3, 1, 7, -5, -1, -1, -9, 
9, 5, 3, 3, -11, -3, 7, 7, 9, -1, -19, -7, 17, 11, 9, -7, -23, 1, -1, -1, 
37, 1, -33, -1, -3, -3, 15, 27, -39, -7, 7, -9, 47, -13, -37, 11, 1, -5, 
51, -9, -37, 19, 17, -5, -1, 13, -43, -5, -3, 13, 95, -29, -107, -19, 55, 
53, 17, -55, -15

with the following perl program:


#!/usr/bin/perl -l

use strict;
use warnings;

sub gcd {
     my ($n,$m)=@_;
     $m ? gcd($m,$n%$m) : $n;
}

my @a=(0,1);

$,=', ';

print $a[1], map {
     my ($n,$m) = ($_,$_+1);
     $a[$n]=do {
 	my $t;
 	$t+=$a[$_] for
 	  grep gcd($m,$_)==1, 1..$n-1;
 	-$t;
     }
} 2..100;

__END__


I have the *impression* of having already seen this sequence, but cannot 
tell for sure...


Michele
-- 
> Di solito vedo persone come te svenute nelle taverne.
Ancor PRIMA che ti sentano l'alito?
- "Cavaliere Verde" su it.discussioni.litigi