A126949 - OEIS

%I #28 Jun 14 2016 03:23:38

%S 5,7,9,10,11,13,14,17,18,19,21,22,23,25,26,27,28,29,31,33,34,35,36,37,

%T 38,39,41,42,43,44,45,46,47,49,50,52,53,54,55,56,57,58,59,61,62,63,65,

%U 66,67,69,70,71,72,73,74,75,76,77,78,79,81,82,83,84,85,86,87,88,89,90

%N Moduli n for which -1 is a (nontrivial) power residue for some power greater than 2, i.e., m^k == -1 (mod n) for some k > 1 and some 1 < m < n-1.

%C The complement of A178751 (within integers > 1). - _M. F. Hasler_, Jun 06 2016

%H Reinhard Zumkeller, <a href="/A126949/b126949.txt">Table of n, a(n) for n = 1..1000</a>

%H Emmanuel Amiot, <a href="http://dx.doi.org/10.1080/17459730802598146">Autosimilar Melodies</a>, J. Math. Music 2 (2008), no. 3, 157-180. DOI: 10.1080/17459730802598146.

%H Emmanuel Amiot, <a href="http://canonsrythmiques.free.fr/pdf/maMuXMelodieAmiot.pdf">Mélodies autosimilaires (Self-Replicating Melodies)</a> (in French).

%e 19 is in the sequence because -1 == 10^9 (mod 19).

%t ord[x_, n_] := Module[{k = 1}, While[k <= EulerPhi[n]/2 && PowerMod[x, k, n] != n - 1, k++ ]; If[PowerMod[x, k, n] == n - 1, k, infinity]] iGeneralise[n_] := Module[{candidats = Range[n - 2]}, candidats = Select[candidats, (GCD[n, # ] == 1) &]; Select[candidats, (ord[ #, n] < n) &] ] sol = {}; Do[If[iGeneralise[n] != {}, AppendTo[sol, n]], {n, 2, 100}]

%o (Haskell)

%o a126949 n = a126949_list !! (n-1)

%o a126949_list = filter h [1..] where

%o    h m = not $ null [(x, e) | x <- [2 .. m - 2], gcd x m == 1,

%o                               e <- [2 .. a000010 m `div` 2],

%o                               x ^ e `mod` m == m - 1]

%o -- _Reinhard Zumkeller_, May 23 2013

%o (PARI) is_A126949(n)={for(x=2,n-2, gcd(x,n)>1&&next; my(t=Mod(x,n)); while(abs(centerlift(t))>1,t*=x); t==-1&&return(x))} \\ (Based on code for A178751 by Ch. Greathouse.) - _M. F. Hasler_, Jun 07 2016

%Y Cf. A008784, A000010.

%K nonn,hear

%O 1,1

%A _Emmanuel Amiot_, Mar 19 2007

%E Edited by _M. F. Hasler_, Jun 06 2016