A065339 -id:A065339 - cp's OEIS frontend

A260730 Numbers n for which A065339(n) > A260728(n).

21, 33, 42, 57, 66, 69, 77, 84, 93, 105, 114, 129, 132, 133, 138, 141, 154, 161, 165, 168, 177, 186, 189, 201, 209, 210, 213, 217, 228, 231, 237, 249, 253, 258, 264, 266, 273, 276, 282, 285, 297, 301, 308, 309, 321, 322, 329, 330, 336, 341, 345, 354, 357, 372, 378, 381, 385, 393, 399, 402, 413, 417, 418, 420, 426, 429, 434, 437, 441, 453, 456, 462, 465, 469, 473, 474, 483, 489, 497, 498, 501, 506, 513, 516, 517, 525, 528, 532, 537, 546, 552

Offset: 1

Antti Karttunen, Aug 12 2015

nonn

Numbers n such that when the exponents in the prime factorization of A097706(n) are added in base-2 they produce at least one carry-bit. In other words, in that set of exponents {e1, e2, ..., en} there is at least one pair e_i, e_j that their binary representations have at least one 1-bit in the same position. (Here i and j are distinct as e_i and e_j are exponents of different primes, although e_i could be equal to e_j. See the examples.)

This differs from A119973 for the first time at n=30 where a(30)=231, term which is not present in A119973. Note that n=231 is the first position where the difference A065339(n) - A260728(n) > 1 as 231 = 3*7*11, a product of three distinct 4k+3 primes, thus A065339(231) = 3, while A260728(231) = 1.

			21 = 3^1 * 7^1 is present, because in its prime factors of the form 4k+3 (which are 3 and 7) the exponents 1 and 1 have at least one 1-bit in the same position, thus producing a carry-bit when summed in base-2.
63 = 3^2 * 7^1 is NOT present, because in its prime factors of the form 4k+3 the exponents 2 and 1 ("10" and "1" in binary) do NOT produce a carry-bit when summed in base-2, as those binary representations do not have any 1's in a common position.
189 = 3^3 * 7^1 is present, because in its prime factors of the form 4k+3 the exponents 3 and 1 ("11" and "1" in binary) have at least one 1-bit in the same position, thus producing a carry-bit when summed in base-2.

Antti Karttunen, Table of n, a(n) for n = 1..10000

Cf. A065339, A260728, A097706, A119973.

A246270 Number of prime factors of the form 4k+3 (counted with multiplicity) in A003961(n): a(n) = A065339(A003961(n)).

Original entry on oeis.org

0, 1, 0, 2, 1, 1, 1, 3, 0, 2, 0, 2, 0, 2, 1, 4, 1, 1, 1, 3, 1, 1, 0, 3, 2, 1, 0, 3, 1, 2, 0, 5, 0, 2, 2, 2, 0, 2, 0, 4, 1, 2, 1, 2, 1, 1, 0, 4, 2, 3, 1, 2, 1, 1, 1, 4, 1, 2, 0, 3, 1, 1, 1, 6, 1, 1, 1, 3, 0, 3, 0, 3, 1, 1, 2, 3, 1, 1, 1, 5, 0, 2, 0, 3, 2, 2, 1, 3, 0, 2, 1, 2, 0, 1, 2, 5

Offset: 1

Antti Karttunen, Aug 21 2014

nonn

Antti Karttunen, Table of n, a(n) for n = 1..10080

Cf. A001222, A003961, A007949, A065339, A246269, A246272.

default(primelimit, 2^22)
A246269(n) = my(f = factor(n)); for (i=1, #f~, f[i, 1] = (nextprime(f[i, 1]+1)%4)); factorback(f);
A246270(n) = bigomega(A246269(n));
for(n=1, 10080, write("b246270.txt", n, " ", A246270(n)));

(define (A246270 n) (A065339 (A003961 n)))

(define (A246270 n) (A007949 (A246269 n)))

a(n) = A065339(A003961(n)).
a(n) = A001222(A246269(n)).
a(n) = A007949(A246269(n)).
Other identities.
If n = u*v, a(n) = a(u)+a(v).
For all n >= 0, a(2^n) = n.

A373594 Lexicographically earliest infinite sequence such that for all i, j >= 1, a(i) = a(j) => f(i) = f(j), where f(n<=3) = n, f(p) = 0 for primes p > 3, and for composite n, f(n) = [A007814(n), A065339(n), A083025(n), A373591(n), A373592(n)].

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 5, 7, 8, 9, 5, 10, 5, 11, 12, 13, 5, 14, 5, 15, 16, 17, 5, 18, 19, 20, 21, 22, 5, 23, 5, 24, 25, 9, 26, 27, 5, 11, 28, 29, 5, 30, 5, 31, 32, 17, 5, 33, 34, 35, 12, 36, 5, 37, 38, 39, 16, 9, 5, 40, 5, 11, 41, 42, 43, 44, 5, 15, 25, 45, 5, 46, 5, 20, 47, 22, 48, 49, 5, 50, 51, 9, 5, 52, 19, 11, 12, 53, 5, 54, 55, 31, 16, 17, 26, 56, 5, 57, 58

Offset: 1

Antti Karttunen, Jun 13 2024

nonn

Restricted growth sequence transform of the function f given in the definition.
Note that for composite n, f(n) can be defined in general as a quintuple vector [v(n), w(n), x(n), y(n), z(n)], where v, w, x, y and z are any five of these six sequences: A007814, A007949, A065339, A083025, A373591, A373592. This follows because A007814(n) + A065339(n) + A083025(n) = A007949(n) + A373591(n) + A373592(n) = A001222(n), so the omitted sixth element can be always worked out from the remaining five.
For all i, j > 1:
  A305900(i) = A305900(j) => a(i) = a(j) => A373595(i) = A373595(j).

Antti Karttunen, Table of n, a(n) for n = 1..100000

Cf. A007814, A007949, A065339, A083025, A373591, A373592.

Cf. also A305900, A373595.

up_to = 100000;
rgs_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), u=1); for(i=1, length(invec), if(mapisdefined(om,invec[i]), my(pp = mapget(om, invec[i])); outvec[i] = outvec[pp] , mapput(om,invec[i],i); outvec[i] = u; u++ )); outvec; };
A007814(n) = valuation(n,2);
A065339(n) = sum(i=1, #n=factor(n)~, (3==n[1, i]%4)*n[2, i]);
A083025(n) = sum(i=1, #n=factor(n)~, (1==n[1, i]%4)*n[2, i]);
A373591(n) = sum(i=1, #n=factor(n)~, (1==n[1, i]%3)*n[2, i]);
A373592(n) = sum(i=1, #n=factor(n)~, (2==n[1, i]%3)*n[2, i]);
Aux373594(n) = if(n<=3, n, if(isprime(n), 0, [A007814(n), A083025(n), A065339(n), A373591(n), A373592(n)]));
v373594 = rgs_transform(vector(up_to, n, Aux373594(n)));
A373594(n) = v373594[n];

A014577 The regular paper-folding sequence (or dragon curve sequence). Alphabet {1,0}.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0

Offset: 0

N. J. A. Sloane, Eric W. Weisstein

a(n) is the complement of the bit to the left of the least significant "1" in the binary expansion of n+1. E.g., n = 3, n+1 = 4 = 100_2, so a(3) = (complement of bit to left of 1) = 1. - Robert L. Brown, Nov 28 2001 [Adjusted to match offset by N. J. A. Sloane, Apr 15 2021]
To construct the sequence: start from 1,(..),0,(..),1,(..),0,(..),1,(..),0,(..),1,(..),0,... and fill undefined places with the sequence itself. - Benoit Cloitre, Jul 08 2007
This is the characteristic function of A091072 - 1. - Gary W. Adamson, Apr 11 2010
Turns (by 90 degrees) of the Heighway dragon which can be rendered as follows: [Init] Set n=0 and direction=0. [Draw] Draw a unit line (in the current direction). Turn left/right if a(n) is zero/nonzero respectively. [Next] Set n=n+1 and goto (draw). See fxtbook link below. - Joerg Arndt, Apr 15 2010
Sequence can be obtained by the L-system with rules L->L1R, R->L0R, 1->1, 0->0, starting with L, and then dropping all L's and R's (see example). - Joerg Arndt, Aug 28 2011
From Gary W. Adamson, Jun 20 2012: (Start)
One half of the infinite Farey tree can be mapped one-to-one onto A014577 since both sequences can be derived directly from the binary. First few terms are
   1,   1,   0,   1,   1,   0,   0,   1,   1,   1, ...
  1/2  2/3  1/3  3/4  3/5  2/5  1/4  4/5  5/7  5/8, ...
Infinite Farey tree fractions can be derived from the binary by appending a repeat of rightmost binary term to the right, then recording the number of runs to obtain the continued fraction representation. Example: 9 = 1001 which becomes 10011 which becomes [1,2,2] = 5/7. (End)
The sequence can be considered as a binomial transform operator for a target sequence S(n). Replace the first 1 in A014577 with the first term in S(n), then for successive "1" term in A014577, map the next higher term in S(n). If "0" in A014577, map the next lower term in S(n). Using the sequence S(n) = (1, 3, 5, 7, ...), we obtain (1), (3, 1), (3, 5, 3, 1), (3, 5, 7, 5, 3, 5, 3, 1), .... Then parse the terms into subsequences of 2^k terms, adding the terms in each string.  We obtain (1, 4, 12, 32, 80, ...), the binomial transform of (1, 3, 5, 7, ...). The 8-bit string has one 1, three 5's, three 7's and one 1) as expected, or (1, 3, 3, 1) dot (1, 3, 5, 7). - Gary W. Adamson, Jun 24 2012
From Gary W. Adamson, May 29 2013: (Start)
The sequence can be generated directly from the lengths of continued fraction representations of fractions in one half of the Stern-Brocot tree (fractions between 0 and 1):
   1/2
   1/3 2/3
   1/4 2/5 3/5 3/4
   1/5 2/7 3/8 3/7 4/7 5/8 5/7 4/5
   ...
and their corresponding continued fraction representations are:
   [2]
   [3] [1,2]
   [4] [2,2] [1,1,2] [1,3]
   [5] [3,2] [2,1,2] [2,3] [1,1,3] [1,1,1,2] [1,2,2] [1,4]
   ...
Record the lengths by rows then reverse rows, getting:
   1,
   2, 1,
   2, 3, 2, 1,
   2, 3, 4, 3, 2, 3, 2, 1,
   ...
start with "1" and if the next term is greater than the current term, record a 1, otherwise 0; getting the present sequence, the Harter-Heighway dragon curve.  (End)
The paper-folding word "110110011100100111011000..." can be created by concatenating the terms of a fixed point of the morphism or string substitution rule: 00 -> 1000, 01 -> 1001, 10 -> 1100 & 11 -> 1101, beginning with "11". - Robert G. Wilson v, Jun 11 2015
From Gary W. Adamson, Jun 04 2021: (Start)
Since the Heighway dragon is composed of right angles, it can be mapped with unit trajectories (Right = 1, Left = (-1), Up = i and Down = -i) on the complex plane where i = sqrt(-1). The initial (0th) iterate is chosen in this case to be the unit line from (0,0) to (-1,0). Then follow the directions below as indicated, resulting in a reflected variant of the dragon curve shown at the Eric Weisstein link. The conjectured system of complex plane trajectories is:
  0   -1
  1   -1, i
  2   -1, i, 1, i
  3   -1, i, 1, i, 1, -i, 1, i
  4   -1, i, 1, i, 1, -i, 1, i, 1, -i, -1, -i, 1, -i, 1, i
  ...
The conjecture succeeds through the 4th iterate. It appears that to generate the (n+1)-th row, bring down the n-th row as the left half of row (n+1). For the right half of row (n+1), bring down the n-th row but change the signs of the first half of row n. For example, to get the complex plane instructions for the third iterate of the dragon curve, bring down (-1, i, 1, i) as the left half, and the right half is (1, -i, 1, i).  (End)
From Gary W. Adamson, Jun 09 2021: (Start)
Partial sums of the iterate trajectories produce a sequence of complex addresses for unit segments. Partial sums of row 4 are:  -1, (-1+i), i, 2i, (1+2i), (1+i), (2+i), (2+2i), (3+2i), (3+i), (2+i), 2, 3, (3-i), (4-i), 4. (zeros are omitted with terms of the form a+0i).  The reflected variant of the dragon curve has the 0th iterate from (0,0) to (1,0), and the respective addresses simply change the signs of the real terms.  (End)

			1 + x + x^3 + x^4 + x^7 + x^8 + x^9 + x^12 + x^15 + x^16 + x^17 + x^19 + ...
From _Joerg Arndt_, Aug 28 2011: (Start)
Generation via string substitution:
Start: L
Rules:
  L --> L1R
  R --> L0R
  0 --> 0
  1 --> 1
-------------
0:   (#=1)
  L
1:   (#=3)
  L1R
2:   (#=7)
  L1R1L0R
3:   (#=15)
  L1R1L0R1L1R0L0R
4:   (#=31)
  L1R1L0R1L1R0L0R1L1R1L0R0L1R0L0R
5:   (#=63)
  L1R1L0R1L1R0L0R1L1R1L0R0L1R0L0R1L1R1L0R1L1R0L0R0L1R1L0R0L1R0L0R
Drop all L and R to obtain 1101100111001001110110001100100
(End)

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, pp. 155, 182.
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 in Donald E. Knuth, Selected Papers on Fun and Games, CSLI Publications, 2010, pages 571-614.
Michel Dekking, Michel Mendes France, and Alf van der Poorten, "Folds", The Mathematical Intelligencer, 4.3 (1982): 130-138 & front cover, and 4:4 (1982): 173-181 (printed in two parts).
Martin Gardner, Mathematical Magic Show, New York: Vintage, pp. 207-209 and 215-220, 1978.
Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.

Ivan Panchenko, Table of n, a(n) for n = 0..10000
Ibrahim M. Alabdulmohsin, "Analytic Summability Theory", in Summability Calculus: A Comprehensive Theory of Fractional Finite Sums, Springer, Cham, pp 65-91.
Jean-Paul Allouche and Michel Mendès France, Automata and Automatic Sequences, in: F. Axel and D. Gratias (eds), Beyond Quasicrystals. Centre de Physique des Houches, vol 3. Springer, Berlin, Heidelberg, pp. 293-367, 1995; DOI https://doi.org/10.1007/978-3-662-03130-8_11.
Jean-Paul Allouche and Michel Mendès France, Automata and Automatic Sequences, in: Axel F. and Gratias D. (eds), Beyond Quasicrystals. Centre de Physique des Houches, vol 3. Springer, Berlin, Heidelberg, pp. 293-367, 1995; DOI https://doi.org/10.1007/978-3-662-03130-8_11. [Local copy]
Joerg Arndt, Matters Computational (The Fxtbook), pp. 88-92; image of the dragon curve on p. 89.
Paul Barry, Conjectures and results on some generalized Rueppel sequences, arXiv:2107.00442 [math.CO], 2021.
Michael Coons, An Irrationality Measure for Regular Paperfolding Numbers, Journal of Integer Sequences, Vol. 15 (2012), Article #12.1.6.
Danielle Cox and K. McLellan, A problem on generation sets containing Fibonacci numbers, Fib. Quart., 55 (No. 2, 2017), 105-113.
Chandler Davis and Donald E. Knuth, Number Representations and Dragon Curves, Journal of Recreational Mathematics, volume 3, number 2, April 1970, pages 66-81, and number 3, July 1970, pages 133-149. [Cached copy, with permission]
Alexey Garber, On triangular paperfolding patterns, arXiv:1807.05627 [math.CO], 2018.
Franz Gahler and Johan Nilsson, Substitution rules for higher-dimensional paperfolding structures, arXiv:1408.4997 [math.DS], 2014.
Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, and Ciril Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 63. Book's website
Eve Kivivuori, Implementing, analyzing, and benchmarking the Relative Lempel-Ziv compression algorithm, Master's Thesis, Univ. Helsinki (Finland 2023).
Guy Melançon, Factorizing infinite words using Maple, MapleTech journal, (14 Mb) vol. 4, no. 1, 1997, pp. 34-42, esp. p. 36.
Johan Nilsson, The Pattern Complexity of the 2-Dimensional Paperfolding Sequence, arXiv:2409.03068 [math.CO], 2024. See p. 1.
Larry Riddle, Heighway Dragon, Classic Iterated Function Systems.
Luke Schaeffer and Jeffrey Shallit, Closed, Palindromic, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences, Electronic Journal of Combinatorics 23(1) (2016), #P1.25.
Joshua E. S. Socolar and Joan M. Taylor, An aperiodic hexagonal tile, arXiv:1003.4279 [math.CO], 2010.
László Tóth, Evaluating zeta(s) At Odd Positive Integers Using Automatic Dirichlet Series, arXiv:2508.04151 [math.NT], 2025.
Eric Weisstein's World of Mathematics, Dragon curve.
Hans Zantema, Complexity of Automatic Sequences, International Conference on Language and Automata Theory and Applications (LATA 2020): Language and Automata Theory and Applications, 260-271.
Index entries for 2-automatic sequences.
Index entries for sequences obtained by enumerating foldings.
Index entries for sequences related to binary expansion of n.

Essentially the same: A014707, A014709, A014710, A034947, A038189, A082410, A089013, A099545, A112347, A121238, A317335, A317336.
Cf. A059125, A065339, A005811, A220466, A088748, A091072, A343173 (first differences), A343174 (partial sums).
The two bisections are A000035 and the sequence itself.
See A343181 for prefixes of length 2^k-1.

[(1+KroneckerSymbol(-1,n))/2: n in [1..100]]; // Vincenzo Librandi, Aug 05 2015

[Floor(1/2*(1+(-1)^(1/2*((n+1)/2^Valuation(n+1, 2)-1)))): n in [0..100]]; // Vincenzo Librandi, Aug 05 2015

nmax:=98: for p from 0 to ceil(simplify(log[2](nmax))) do for n from 0 to ceil(nmax/(p+2))+1 do a((2*n+1)*2^p-1) := (n+1) mod 2 od: od: seq(a(n), n=0..nmax); # Johannes W. Meijer, Jan 28 2013
a014577 := proc(n) local p,s1,s2,i;
if n=0 then return(1); fi;
s1:=convert(n,base,2); s2:=nops(s1);
for i from 1 to s2 do if s1[i]=1 then p:=i; break; fi; od:
if p <= s2-1 then 1-s1[p+1]; else 1; fi; end;
[seq(a014577(i),i=1..120)]; # N. J. A. Sloane, Apr 08 2021
# third Maple program:
a:= n-> 1-irem(iquo((n+1)/2^padic[ordp](n+1, 2), 2), 2):
seq(a(n), n=0..120);  # Alois P. Heinz, Apr 08 2021

a[n_] := Boole[EvenQ[((n+1)/2^IntegerExponent[n+1, 2]-1)/2]]; Table[a[n], {n, 0, 98}] (* Jean-François Alcover, Feb 16 2012, after Gary W. Adamson, updated Nov 21 2014 *)
Table[1-(((Mod[#1,2^(#2+2)]/2^#2)&[n,IntegerExponent[n,2]])-1)/2,{n,1,100,1}] (* WolframAlpha compatible code; Robert L. Brown, Jan 06 2015 *)
MapThread[(a[x_/;IntegerQ[(x-#1)/4]]:= #2)&,{{1,3},{1,0}}];a[x_/;IntegerQ[x/2]]:=a[x/2];a/@ Range[100] (* Bradley Klee, Aug 04 2015 *)
(1 + JacobiSymbol[-1, Range[100]])/2 (* Paolo Xausa, May 22 2024 *)
Array[Boole[BitAnd[#, BitAnd[#, -#]*2] == 0] &, 100] (* Paolo Xausa, May 22 2024, after Joerg Arndt C++ code *)

{a(n) = if( n%2, a(n\2), 1 - (n/2%2))} /* Michael Somos, Feb 05 2012 */

a(n)=1/2*(1+(-1)^(1/2*((n+1)/2^valuation(n+1,2)-1))) \\ Ralf Stephan, Sep 02 2013

a(n)=!bittest(n+1,valuation(n+1,2)+1); \\ Robert L. Brown, Jul 07 2025

def A014577(n):
    s = bin(n+1)[2:]
    m = len(s)
    i = s[::-1].find('1')
    return 1-int(s[m-i-2]) if m-i-2 >= 0 else 1 # Chai Wah Wu, Apr 08 2021

a(n) = (1+Jacobi(-1,n+1))/2 (cf. A034947). - N. J. A. Sloane, Jul 27 2012 [Adjusted to match offset by Peter Munn, Jul 01 2022]
Set a=1, b=0, S(0)=a, S(n+1) = S(n), a, F(S(n)), where F(x) reverses x and then interchanges a and b; sequence is limit S(infinity).
From Ralf Stephan, Jul 03 2003: (Start)
a(4*n) = 1, a(4*n+2) = 0, a(2*n+1) = a(n).
a(n) = 1 - A014707(n) = 2 - A014709(n) = A014710(n) - 1. (End)
Set a=1, b=0, S(0)=a, S(n+1)=S(n), a, M(S(n)), where M(S) is S but the bit in the middle position flipped. (Proof via isomorphism of both formulas to a modified string substitution.) - Benjamin Heiland, Dec 11 2011
a(n) = 1 if A005811(n+1) > A005811(n), otherwise a(n) = 0. - Gary W. Adamson, Jun 20 2012
a((2*n+1)*2^p-1) = (n+1) mod 2, p >= 0. - Johannes W. Meijer, Jan 28 2013
G.f. g(x) satisfies g(x) = x*g(x^2) + 1/(1-x^4). - Robert Israel, Jan 06 2015
a(n) = 1 - A065339(n+1) mod 2. - Peter Munn, Jun 29 2022
From A.H.M. Smeets, Mar 19 2023: (Start)
a(n) = 1 - A038189(n+1).
a(n) = A082410(n+2).
a(n) = 1 - A089013(n+1)
a(n) = (3 - A099545(n+1))/2.
a(n) = (A112347(n+1) + 1)/2.
a(n) = (A121238(n+1) + 1)/2.
a(n) = (A317335(n) + 2)/3.
a(n) = (A317336(n) + 10)/3. (End)
Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = 1/2. - Amiram Eldar, Sep 14 2024

More terms from Ralf Stephan, Jul 03 2003

A083025 Number of primes congruent to 1 modulo 4 dividing n (with multiplicity).

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 2, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 2, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 2, 0, 0, 1, 0, 1, 0, 0, 1, 1, 2, 0, 0, 1, 0, 1, 0, 1, 0, 0, 2, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 2, 1, 1, 0, 1, 1

Offset: 1

Reinhard Zumkeller, Oct 29 2001

David A. Cox, "Primes of the Form x^2 + n y^2", Wiley, 1989, p. 61.

T. D. Noe, Table of n, a(n) for n = 1..10000

First differs from A046080 at n=65.

Cf. A001222, A007814, A027746, A065339 (== 3 (mod 4)), A378879 (=2,3 (mod 4)), A005089 (without multiplicity).

a083025 1 = 0
a083025 n = length [x | x <- a027746_row n, mod x 4 == 1]
-- Reinhard Zumkeller, Jan 10 2012

A083025 := proc(n)
    a := 0 ;
    for f in ifactors(n)[2] do
        if op(1,f) mod 4 = 1 then
            a := a+op(2,f) ;
        end if;
    end do:
    a ;
end proc: # R. J. Mathar, Dec 16 2011

f[n_]:=Plus@@Last/@Select[If[n==1,{},FactorInteger[n]],Mod[#[[1]],4]==1&]; Table[f[n],{n,100}] (* Ray Chandler, Dec 18 2011 *)

A083025(n)=sum(i=1,#n=factor(n)~,if(n[1,i]%4==1,n[2,i]))  \\ M. F. Hasler, Apr 16 2012

a(n) = A001222(n) - A007814(n) - A065339(n).

Totally additive with a(2) = 0, a(p) = 1 if p == 1 (mod 4), and a(p) = 0 if p == 3 (mod 4). - Amiram Eldar, Jun 17 2024

A034947 Jacobi (or Kronecker) symbol (-1/n).

Original entry on oeis.org

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, 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, 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

Offset: 1

N. J. A. Sloane

Also the regular paper-folding sequence.
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
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
Partial sums = A005811 starting (1, 2, 1, 2, 3, 2, 1, 2, 3, ...). - Gary W. Adamson, Jul 23 2008
The congruence in {-1,1} of the odd part of n modulo 4 (Cf. A099545). - Peter Munn, Jul 09 2022

			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 + ...

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, pp. 155, 182.
H. Cohen, Course in Computational Number Theory, p. 28.

N. J. A. Sloane, Table of n, a(n) for n = 1..10000
J.-P. Allouche, G.-N. Han, and Jeffrey Shallit, On some conjectures of P. Barry, arXiv:2006.08909 [math.NT], 2020.
J.-P. Allouche and Jonathan Sondow, Summation of rational series twisted by strongly B-multiplicative coefficients, Electron. J. Combin., 22 #1 (2015) P1.59; see p. 8.
J.-P. Allouche and Jonathan Sondow, Summation of rational series twisted by strongly B-multiplicative coefficients, arXiv:1408.5770 [math.NT] v4, 2015; see p. 9.
Jean-Paul Allouche and Leo Goldmakher, Mock characters and the Kronecker symbol, arXiv:1608.03957 [math.NT], 2016.
L. Almodovar, V. H. Moll, H. Quand, Infinite products arising in paperfolding, JIS 19 (2016) # 16.5.1 eq. (1)
Joerg Arndt, Matters Computational (The Fxtbook), section 38.8.4 Differences of the sum of Gray code digits, coefficients of polynomials L.
Danielle Cox and K. McLellan, A problem on generation sets containing Fibonacci numbers, Fib. Quart., 55 (No. 2, 2017), 105-113.
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, Selected Papers on Fun and Games, CSLI Publications, 2010, pages 571-614. a(n) = d(n) at equation 3.1.
Chandler Davis and Donald E. Knuth, Number Representations and Dragon Curves, Journal of Recreational Mathematics, volume 3, number 2, April 1970, pages 66-81, and number 3, July 1970, pages 133-149. [Cached copy, with permission]
A. Iványi, Leader election in synchronous networks, Acta Univ. Sapientiae, Mathematica, 5, 2 (2013) 54-82.
Jeffrey Shallit, Cloitre's Self-Generating Sequence, arXiv:2501.00784 [math.CO], 2025. See page 4.
Eric Weisstein's World of Mathematics, Kronecker Symbol.
Index entries for sequences obtained by enumerating foldings.

Cf. A000265, A005811, A000364, A008836, A065339, A097706, A099545, A209615.
Moebius transform of A035184.
Cf. A091072 (indices of 1), A091067 (indices of -1), A371594 (indices of run starts).
The following are all essentially the same sequence: A014577, A014707, A014709, A014710, A034947, A038189, A082410. - N. J. A. Sloane, Jul 27 2012

[KroneckerSymbol(-1,n): n in [1..100]]; // Vincenzo Librandi, Aug 16 2016

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

Table[KroneckerSymbol[ -1, n], {n, 0, 100}] (* Corrected by Jean-François Alcover, Dec 04 2013 *)

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

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

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 */

a(n) = if(n%2==0, a(n/2), (n+2)%4-2) \\ Peter Munn, Jul 09 2022

def A034947(n):
    s = bin(n)[2:]
    m = len(s)
    i = s[::-1].find('1')
    return 1-2*int(s[m-i-2]) if m-i-2 >= 0 else 1 # Chai Wah Wu, Apr 08 2021

def A034947(n): return -1 if n>>(-n&n).bit_length()&1 else 1 # Chai Wah Wu, Feb 26 2025

Multiplicative with a(2^e) = 1, a(p^e) = (-1)^(e*(p-1)/2) if p>2.
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.
a(prime(n)) = A070750(n) for n > 1. - T. D. Noe, Nov 08 2004
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
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
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
Dirichlet g.f.: beta(s)/(1-2^(-s)) = L(chi_2(4),s)/(1-2^(-s)). - Ralf Stephan, Mar 27 2015
a(n) = A209615(n) * (-1)^(v2(n)), where v2(n) = A007814(n) is the 2-adic valuation of n. - Jianing Song, Apr 24 2021
a(n) = 2 - A099545(n) == A000265(n) (mod 4). - Peter Munn, Jun 22 2022 and Jul 09 2022

A038189 Bit to left of least significant 1-bit in binary expansion of n.

Original entry on oeis.org

0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1

Offset: 0

Fred Lunnon, Dec 11 1999

Characteristic function of A091067.
Image, under the coding i -> floor(i/2), of the fixed point, starting with 0, of the morphism 0 -> 01, 1 -> 02, 2 -> 32, 3 -> 31. - Jeffrey Shallit, May 15 2016
Restricted to the positive integers, completely additive modulo 2. - Peter Munn, Jun 20 2022
If a(n) is defined as 1-a(-n) for all n<0, then a(n) = a(2*n), a(4*n+1) = 0, a(4*n+3) = 1 for all n in Z. - Michael Somos, Oct 05 2024

			a(6) = 1 since 6 = 110 and bit before rightmost 1 is a 1.

Jean-Paul Allouche and Jeffrey O. Shallit, Automatic sequences, Cambridge, 2003, sect. 5.1.6

Ivan Panchenko, Table of n, a(n) for n = 0..10000
Michael Gilleland, Some Self-Similar Integer Sequences
Index entries for characteristic functions
Index entries for sequences related to binary expansion of n
Index entries for sequences obtained by enumerating foldings

Cf. A038190, A065339.
A014707(n)=a(n+1). A014577(n)=1-a(n+1).
The following are all essentially the same sequence: A014577, A014707, A014709, A014710, A034947, A038189, A082410. - N. J. A. Sloane, Jul 27 2012
Related sequences A301848, A301849, A301850. - Fred Lunnon, Mar 27 2018

int a(int n) { return (n & ((n&-n)<<1)) ? 1 : 0; } /* from Russ Cox */

function a (n)
  if n eq 0 then return 0; // alternatively,  return 1;
  else while IsEven(n) do n := n div 2; end while; end if;
  return n div 2 mod 2; end function;
  nlo := 0; nhi := 32;
  [a(n) : n in [nlo..nhi] ]; //  Fred Lunnon, Mar 27 2018

A038189 := proc(n)
    option remember;
    if n = 0 then
        0 ;
    elif type(n,'even') then
        procname(n/2) ;
    elif modp(n,4) = 1 then
        0 ;
    else
        1 ;
    end if;
end proc:
seq(A038189(n),n=0..100) ; # R. J. Mathar, Mar 30 2018

f[n_] := Block[{id2 = Join[{0}, IntegerDigits[n, 2]]}, While[ id2[[-1]] == 0, id2 = Most@ id2]; id2[[-2]]]; f[0] = 0; Array[f, 105, 0] (* Robert G. Wilson v, Apr 14 2009 and fixed Feb 27 2014 *)
f[n_] := f[n] = Switch[Mod[n, 4], 0, f[n/2], 1, 0, 2, f[n/2], 3, 1]; f[0] = 0; Array[f, 105, 0] (* Robert G. Wilson v, Apr 14 2009, fixed Feb 27 2014 *)
a[ n_] := If[n==0, 0, Mod[(n/2^IntegerExponent[n, 2]-1)/2, 2]]; (* Michael Somos, Oct 05 2024 *)

{a(n) = if(n==0, 0, ((n/2^valuation(n,2)-1)/2)%2)}; /* Michael Somos, Sep 22 2005 */

a(n) = if(n<3, 0, prod(m=1,n, kronecker(-n,m)==kronecker(m,n))) /* Michael Somos, Sep 22 2005 */

A038189(n)=bittest(n,valuation(n,2)+1) \\ M. F. Hasler, Aug 06 2015

a(n)=my(h=bitand(n,-n));n=bitand(n,h<<1);n!=0; \\ Joerg Arndt, Apr 09 2021

def A038189(n):
    s = bin(n)[2:]
    m = len(s)
    i = s[::-1].find('1')
    return int(s[m-i-2]) if m-i-2 >= 0 else 0 # Chai Wah Wu, Apr 08 2021

def a(n): return 1 if (n & ((n&-n)<<1)) else 0
print([a(n) for n in range(108)]) # Michael S. Branicky, Feb 06 2025 after Russ Cox

a(0) = 0, a(2*n) = a(n) for n>0, a(4*n+1) = 0, a(4*n+3) = 1.
G.f.: Sum_{k>=0} t^3/(1-t^4), where t=x^2^k. Parity of A025480. For n >= 1, a(n) = 1/2 * (1 - (-1)^A025480(n-1)). - Ralf Stephan, Jan 04 2004 [index adjusted by Peter Munn, Jun 22 2022]
a(n) = 1 if Kronecker(-n,m)=Kronecker(m,n) for all m, otherwise a(n)=0. - Michael Somos, Sep 22 2005
a(n) = 1 iff A164677(n) < 0. - M. F. Hasler, Aug 06 2015
For n >= 1, a(n) = A065339(n) mod 2. - Peter Munn, Jun 20 2022
From A.H.M. Smeets, Mar 08 2023: (Start)
a(n+1) = 1 - A014577(n) for n >= 0.
a(n+1) = 2 - A014710(n) for n >= 0.
a(n) = (1 - A034947(n))/2 for n > 0. (End)
Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = 1/2. - Amiram Eldar, Aug 30 2024

More terms from David W. Wilson

Definition corrected by Russ Cox and Ralf Stephan, Nov 08 2004

A065338 a(1) = 1, a(p) = p mod 4 for p prime and a(u * v) = a(u) * a(v) for u, v > 0.

Original entry on oeis.org

1, 2, 3, 4, 1, 6, 3, 8, 9, 2, 3, 12, 1, 6, 3, 16, 1, 18, 3, 4, 9, 6, 3, 24, 1, 2, 27, 12, 1, 6, 3, 32, 9, 2, 3, 36, 1, 6, 3, 8, 1, 18, 3, 12, 9, 6, 3, 48, 9, 2, 3, 4, 1, 54, 3, 24, 9, 2, 3, 12, 1, 6, 27, 64, 1, 18, 3, 4, 9, 6, 3, 72, 1, 2, 3, 12, 9, 6, 3, 16, 81, 2, 3, 36, 1, 6, 3, 24, 1, 18, 3

Offset: 1

Reinhard Zumkeller, Oct 29 2001

			a(120) = a(2*2*2*3*5) = a(2)*a(2)*a(2)*a(3)*a(5) = 2*2*2*3*1 = 24.
a(150) = a(2*3*5*5) = a(2)*a(3)*a(5)*a(5) = 2*3*1*1 = 6.
a(210) = a(2*3*5*7) = a(2)*a(3)*a(5)*a(7) = 2*3*1*3 = 18.

T. D. Noe, Table of n, a(n) for n = 1..1000

Cf. A039702, A000040, A003586, A007814, A065339, A065331.

a065338 1 = 1
a065338 n = (spf `mod` 4) * a065338 (n `div` spf) where spf = a020639 n
-- Reinhard Zumkeller, Nov 18 2011

a[1] = 1; a[n_] := a[n] = Mod[p = FactorInteger[n][[1, 1]], 4]*a[n/p]; Table[ a[n], {n, 1, 100} ] (* Jean-François Alcover, Jan 20 2012 *)

a(n)=my(f=factor(n)); prod(i=1,#f~, (f[i,1]%4)^f[i,2]) \\ Charles R Greathouse IV, Feb 07 2017

a(n) = 1 if n = 1, otherwise (A020639(n) mod 4) * n / A020639(n).
a(n) = (2^A007814(n)) * (3^A065339(n)).
a(n) <= n.
a(a(n)) = a(n).
a(x) = x iff x = 2^i * 3^j for i, j >= 0.
a(A003586(n)) = A003586(n).
a(A065331(n)) = A065331(n).
a(A004613(n)) = 1; A065333(a(n)) = 1. - Reinhard Zumkeller, Jul 10 2010
Dirichlet g.f.: (1/(1-2^(-s+1))) * Product_{prime p=4k+1} (1/(1-p^(-s))) * Product_{prime p=4k+3} 1/(1-3*p^(-s)). - Ralf Stephan, Mar 28 2015

A078458 Total number of factors in a factorization of n into Gaussian primes.

Original entry on oeis.org

0, 2, 1, 4, 2, 3, 1, 6, 2, 4, 1, 5, 2, 3, 3, 8, 2, 4, 1, 6, 2, 3, 1, 7, 4, 4, 3, 5, 2, 5, 1, 10, 2, 4, 3, 6, 2, 3, 3, 8, 2, 4, 1, 5, 4, 3, 1, 9, 2, 6, 3, 6, 2, 5, 3, 7, 2, 4, 1, 7, 2, 3, 3, 12, 4, 4, 1, 6, 2, 5, 1, 8, 2, 4, 5, 5, 2, 5, 1, 10, 4, 4, 1, 6, 4, 3, 3, 7, 2, 6, 3, 5, 2, 3, 3, 11, 2, 4, 3, 8, 2, 5, 1, 8

Offset: 1

N. J. A. Sloane, Jan 11 2003

a(n)+1 is also the total number of factors in a factorization of n+n*i into Gaussian primes. - Jason Kimberley, Dec 17 2011

Record high values are at a(2^k) = 2*k for k = 0, 1, 2, ... . - Bill McEachen, Oct 11 2022

			2 = (1+i)*(1-i), so a(2) = 2; 9 = 3*3, so a(9) = 2.
a(1006655265000) = a(2^3*3^2*5^4*7^5*11^3) = 3*a(2)+2*a(3)+4*a(5)+5*a(7)+3*a(11) = 3*2+2*1+4*2+5*1+3*1 = 24. - _Vladeta Jovovic_, Jan 20 2003

T. D. Noe, Table of n, a(n) for n = 1..10000
Michael Somos, PARI program for finding prime decomposition of Gaussian integers.
Eric Weisstein's World of Mathematics, Gaussian Prime.
Index entries for Gaussian integers and primes.

Cf. A078908-A078911, A007814, A065339, A083025.
Cf. A239626, A239627 (including units).
Equivalent of arithmetic functions in the ring of Gaussian integers (the corresponding functions in the ring of integers are in the parentheses): A062327 ("d", A000005), A317797 ("sigma", A000203), A079458 ("phi", A000010), A227334 ("psi", A002322), A086275 ("omega", A001221), this sequence ("Omega", A001222), A318608 ("mu", A008683).
Equivalent in the ring of Eisenstein integers: A319444.

Join[{0}, Table[f = FactorInteger[n, GaussianIntegers -> True]; cnt = Total[Transpose[f][[2]]]; If[MemberQ[{-1, I, -I}, f[[1, 1]]], cnt--]; cnt, {n, 2, 100}]] (* T. D. Noe, Mar 31 2014 *)
a[n_]:=PrimeOmega[n, GaussianIntegers -> True]; Array[a,104] (* Stefano Spezia, Sep 29 2024 *)

a(n)=my(f=factor(n)); sum(i=1,#f~,if(f[i,1]%4==3,1,2)*f[i,2]) \\ Charles R Greathouse IV, Mar 31 2014

Fully additive with a(p)=2 if p=2 or p mod 4=1 and a(p)=1 if p mod 4=3. - Vladeta Jovovic, Jan 20 2003

a(n) depends on the number of primes of the forms 4k+1 (A083025) and 4k-1 (A065339) and on the highest power of 2 dividing n (A007814): a(n) = 2*A007814(n) + 2*A083025(n) + A065339(n). - T. D. Noe, Jul 14 2003

More terms from Vladeta Jovovic, Jan 12 2003

A097706 Part of n composed of prime factors of form 4k+3.

Original entry on oeis.org

1, 1, 3, 1, 1, 3, 7, 1, 9, 1, 11, 3, 1, 7, 3, 1, 1, 9, 19, 1, 21, 11, 23, 3, 1, 1, 27, 7, 1, 3, 31, 1, 33, 1, 7, 9, 1, 19, 3, 1, 1, 21, 43, 11, 9, 23, 47, 3, 49, 1, 3, 1, 1, 27, 11, 7, 57, 1, 59, 3, 1, 31, 63, 1, 1, 33, 67, 1, 69, 7, 71, 9, 1, 1, 3, 19, 77, 3, 79, 1, 81, 1, 83, 21

Offset: 1

Ralf Stephan, Aug 30 2004

Largest term of A004614 that divides n. - Peter Munn, Apr 15 2021

Alois P. Heinz, Table of n, a(n) for n = 1..10000

Equivalent sequence for distinct prime factors: A170819.
Equivalent sequences for prime factors of other forms: A000265 (2k+1), A170818 (4k+1), A072436 (not 4k+3), A248909 (6k+1), A343431 (6k+5).
Range of values: A004614.
Positions of 1's: A072437.
Cf. also A065338, A065339, A260728, A286363.

a:= n-> mul(`if`(irem(i[1], 4)=3, i[1]^i[2], 1), i=ifactors(n)[2]):
seq(a(n), n=1..100);  # Alois P. Heinz, Jun 09 2014

a[n_] := Product[{p, e} = pe; If[Mod[p, 4] == 3, p^e, 1], {pe, FactorInteger[n]}]; Array[a, 100] (* Jean-François Alcover, Jun 16 2015, updated May 29 2019 *)

a(n)=local(f); f=factor(n); prod(k=1, matsize(f)[1], if(f[k, 1]%4<>3, 1, f[k, 1]^f[k, 2]))

from sympy import factorint
from operator import mul
def a072436(n):
    f=factorint(n)
    return 1 if n == 1 else reduce(mul, [1 if i%4==3 else i**f[i] for i in f])
def a(n): return n/a072436(n) # Indranil Ghosh, May 08 2017

from math import prod
from sympy import factorint
def A097706(n): return prod(p**e for p, e in factorint(n).items() if p & 3 == 3) # Chai Wah Wu, Jun 28 2022

a(n) = n/A072436(n).
a(A004614(n)) = A004614(n).
a(A072437(n)) = 1.
a(n) = A000265(n)/A170818(n). - Peter Munn, Apr 15 2021

cp's OEIS Frontend

A260730 Numbers n for which A065339(n) > A260728(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A246270 Number of prime factors of the form 4k+3 (counted with multiplicity) in A003961(n): a(n) = A065339(A003961(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Scheme

Scheme

Formula

A373594 Lexicographically earliest infinite sequence such that for all i, j >= 1, a(i) = a(j) => f(i) = f(j), where f(n<=3) = n, f(p) = 0 for primes p > 3, and for composite n, f(n) = [A007814(n), A065339(n), A083025(n), A373591(n), A373592(n)].

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A014577 The regular paper-folding sequence (or dragon curve sequence). Alphabet {1,0}.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

Extensions

A083025 Number of primes congruent to 1 modulo 4 dividing n (with multiplicity).

Views

Author

Keywords

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

A034947 Jacobi (or Kronecker) symbol (-1/n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

Python