login
Jacobi (or Kronecker) symbol (-1/n).
30

%I #134 Apr 13 2024 09:02:37

%S 1,1,-1,1,1,-1,-1,1,1,1,-1,-1,1,-1,-1,1,1,1,-1,1,1,-1,-1,-1,1,1,-1,-1,

%T 1,-1,-1,1,1,1,-1,1,1,-1,-1,1,1,1,-1,-1,1,-1,-1,-1,1,1,-1,1,1,-1,-1,

%U -1,1,1,-1,-1,1,-1,-1,1,1,1,-1,1,1,-1,-1,1,1,1,-1,-1,1,-1,-1,1,1

%N Jacobi (or Kronecker) symbol (-1/n).

%C Also the regular paper-folding sequence.

%C For a proof that a(n) equals the paper-folding sequence, see Allouche and Sondow, arXiv v4. - _Jean-Paul Allouche_ and _Jonathan Sondow_, May 19 2015

%C It appears that, replacing +1 with 0 and -1 with 1, we obtain A038189. Alternatively, replacing -1 with 0 we obtain (allowing for offset) A014577. - _Jeremy Gardiner_, Nov 08 2004

%C Partial sums = A005811 starting (1, 2, 1, 2, 3, 2, 1, 2, 3, ...). - _Gary W. Adamson_, Jul 23 2008

%C The congruence in {-1,1} of the odd part of n modulo 4 (Cf. A099545). - _Peter Munn_, Jul 09 2022

%D J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, pp. 155, 182.

%D H. Cohen, Course in Computational Number Theory, p. 28.

%H N. J. A. Sloane, <a href="/A034947/b034947.txt">Table of n, a(n) for n = 1..10000</a>

%H J.-P. Allouche, G.-N. Han, and J. Shallit, <a href="https://arxiv.org/abs/2006.08909">On some conjectures of P. Barry</a>, arXiv:2006.08909 [math.NT], 2020.

%H J.-P. Allouche and Jonathan Sondow, <a href="https://doi.org/10.37236/4630">Summation of rational series twisted by strongly B-multiplicative coefficients</a>, Electron. J. Combin., 22 #1 (2015) P1.59; see p. 8.

%H J.-P. Allouche and Jonathan Sondow, <a href="http://arxiv.org/abs/1408.5770">Summation of rational series twisted by strongly B-multiplicative coefficients</a>, arXiv:1408.5770 [math.NT] v4, 2015; see p. 9.

%H Jean-Paul Allouche and Leo Goldmakher, <a href="http://arxiv.org/abs/1608.03957">Mock characters and the Kronecker symbol</a>, arXiv:1608.03957 [math.NT], 2016.

%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, section 38.8.4 Differences of the sum of Gray code digits, coefficients of polynomials L.

%H Danielle Cox and K. McLellan, <a href="https://www.fq.math.ca/Papers1/55-2/CoxMcLellan021717.pdf">A problem on generation sets containing Fibonacci numbers</a>, Fib. Quart., 55 (No. 2, 2017), 105-113.

%H Chandler Davis and Donald E. Knuth, Number Representations and Dragon Curves -- I and II, Journal of Recreational Mathematics, volume 3, number 2, April 1970, pages 66-81, and number 3, July 1970, pages 133-149. Reprinted with addendum in Donald E. Knuth, <a href="http://www-cs-faculty.stanford.edu/~uno/fg.html">Selected Papers on Fun and Games</a>, CSLI Publications, 2010, pages 571-614. a(n) = d(n) at equation 3.1.

%H A. Iványi, <a href="http://www.emis.de/journals/AUSM/C5-1/math51-5.pdf">Leader election in synchronous networks</a>, Acta Univ. Sapientiae, Mathematica, 5, 2 (2013) 54-82.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/KroneckerSymbol.html">Kronecker Symbol</a>

%H <a href="/index/Fo#fold">Index entries for sequences obtained by enumerating foldings</a>

%F Multiplicative with a(2^e) = 1, a(p^e) = (-1)^(e*(p-1)/2) if p>2.

%F a(2*n) = a(n), a(4*n+1) = 1, a(4*n+3) = -1, a(-n) = -a(n). a(n) = 2*A014577(n-1)-1.

%F a(prime(n)) = A070750(n) for n > 1. - _T. D. Noe_, Nov 08 2004

%F This sequence can be constructed by starting with w = "empty string", and repeatedly applying the map w -> w 1 reverse(-w) [See Allouche and Shallit p. 182]. - _N. J. A. Sloane_, Jul 27 2012

%F a(n) = (-1)^A065339(n) = lambda(A097706(n)), where A065339(n) is number of primes of the form 4*m + 3 dividing n (counted with multiplicity) and lambda is Liouville's function, A008836. - _Arkadiusz Wesolowski_, Nov 05 2013 and _Peter Munn_, Jun 22 2022

%F Sum_{n>=1} a(n)/n = Pi/2, due to F. von Haeseler; more generally, Sum_{n>=1} a(n)/n^(2*d+1) = Pi^(2*d+1)*A000364(d)/(2^(2*d+2)-2)(2*d)! for d >= 0; see Allouche and Sondow, 2015. - _Jean-Paul Allouche_ and _Jonathan Sondow_, Mar 20 2015

%F Dirichlet g.f.: beta(s)/(1-2^(-s)) = L(chi_2(4),s)/(1-2^(-s)). - _Ralf Stephan_, Mar 27 2015

%F a(n) = A209615(n) * (-1)^(v2(n)), where v2(n) = A007814(n) is the 2-adic valuation of n. - _Jianing Song_, Apr 24 2021

%F a(n) = 2 - A099545(n) == A000265(n) (mod 4). - _Peter Munn_, Jun 22 2022 and Jul 09 2022

%e G.f. = x + x^2 - x^3 + x^4 + x^5 - x^6 - x^7 + x^8 + x^9 + x^10 - x^11 - x^12 + ...

%p with(numtheory): A034947 := n->jacobi(-1,n);

%t Table[KroneckerSymbol[ -1, n], {n, 0, 100}] (* Corrected by _Jean-François Alcover_, Dec 04 2013 *)

%o (PARI) {a(n) = kronecker(-1, n)};

%o (PARI) for(n=1, 81, f=factor(n); print1((-1)^sum(s=1, omega(n), f[s, 2]*(Mod(f[s, 1], 4)==3)), ", ")); \\ _Arkadiusz Wesolowski_, Nov 05 2013

%o (PARI) a(n)=direuler(p=1,n,if(p==2,1/(1-kronecker(-4, p)*X)/(1-X),1/(1-kronecker(-4, p)*X))) /* _Ralf Stephan_, Mar 27 2015 */

%o (Magma) [KroneckerSymbol(-1,n): n in [1..100]]; // _Vincenzo Librandi_, Aug 16 2016

%o (Python)

%o def A034947(n):

%o s = bin(n)[2:]

%o m = len(s)

%o i = s[::-1].find('1')

%o return 1-2*int(s[m-i-2]) if m-i-2 >= 0 else 1 # _Chai Wah Wu_, Apr 08 2021

%o (PARI)

%o a(n) = if(n%2==0, a(n/2), (n+2)%4-2) \\ _Peter Munn_, Jul 09 2022

%Y Cf. A000265, A005811, A000364, A008836, A065339, A097706, A099545, A209615.

%Y Moebius transform of A035184.

%Y Cf. A091072 (indices of 1), A091067 (indices of -1), A371594 (indices of run starts).

%Y The following are all essentially the same sequence: A014577, A014707, A014709, A014710, A034947, A038189, A082410. - _N. J. A. Sloane_, Jul 27 2012

%K sign,nice,easy,mult

%O 1,1

%A _N. J. A. Sloane_