A004198 -id:A004198 - cp's OEIS frontend

A019565 The squarefree numbers ordered lexicographically by their prime factorization (with factors written in decreasing order). a(n) = Product_{k in I} prime(k+1), where I is the set of indices of nonzero binary digits in n = Sum_{k in I} 2^k.

1, 2, 3, 6, 5, 10, 15, 30, 7, 14, 21, 42, 35, 70, 105, 210, 11, 22, 33, 66, 55, 110, 165, 330, 77, 154, 231, 462, 385, 770, 1155, 2310, 13, 26, 39, 78, 65, 130, 195, 390, 91, 182, 273, 546, 455, 910, 1365, 2730, 143, 286, 429, 858, 715, 1430, 2145, 4290

Offset: 0

Marc LeBrun

A permutation of the squarefree numbers A005117. The missing positive numbers are in A013929. - Alois P. Heinz, Sep 06 2014
From Antti Karttunen, Apr 18 & 19 2017: (Start)
Because a(n) toggles the parity of n there are neither fixed points nor any cycles of odd length.
Conjecture: there are no finite cycles of any length. My grounds for this conjecture: any finite cycle in this sequence, if such cycles exist at all, must have at least one member that occurs somewhere in A285319, the terms that seem already to be quite rare. Moreover, any such a number n should satisfy in addition to A019565(n) < n also that A048675^{k}(n) is squarefree, not just for k=0, 1 but for all k >= 0. As there is on average a probability of only 6/(Pi^2) = 0.6079... that any further term encountered on the trajectory of A048675 is squarefree, the total chance that all of them would be squarefree (which is required from the elements of A019565-cycles) is soon minuscule, especially as A048675 is not very tightly bounded (many trajectories seem to skyrocket, at least initially). I am also assuming that usually there is no significant correlation between the binary expansions of n and A048675(n) (apart from their least significant bits), or, for that matter, between their prime factorizations.
See also the slightly stronger conjecture in A285320, which implies that there would neither be any two-way infinite cycles.
If either of the conjectures is false (there are cycles), then certainly neither sequence A285332 nor its inverse A285331 can be a permutation of natural numbers. (End)
The conjecture made in A087207 (see also A288569) implies the two conjectures mentioned above. A further constraint for cycles is that in any A019565-trajectory which starts from a squarefree number (A005117), every other term is of the form 4k+2, while every other term is of the form 6k+3. - Antti Karttunen, Jun 18 2017
The sequence satisfies the exponential function identity, a(x + y) = a(x) * a(y), whenever x and y do not have a 1-bit in the same position, i.e., when A004198(x,y) = 0. See also A283475. - Antti Karttunen, Oct 31 2019
The above identity becomes unconditional if binary exclusive OR, A003987(.,.), is substituted for addition, and A059897(.,.), a multiplicative equivalent of A003987, is substituted for multiplication. This gives us a(A003987(x,y)) = A059897(a(x), a(y)). - Peter Munn, Nov 18 2019
Also the Heinz number of the binary indices of n, where the Heinz number of a sequence (y_1,...,y_k) is prime(y_1)*...*prime(y_k), and a number's binary indices (A048793) are the positions of 1's in its reversed binary expansion. - Gus Wiseman, Dec 28 2022

			5 = 2^2+2^0, e_1 = 2, e_2 = 0, prime(2+1) = prime(3) = 5, prime(0+1) = prime(1) = 2, so a(5) = 5*2 = 10.
From _Philippe Deléham_, Jun 03 2015: (Start)
This sequence regarded as a triangle withs rows of lengths 1, 1, 2, 4, 8, 16, ...:
   1;
   2;
   3,  6;
   5, 10, 15, 30;
   7, 14, 21, 42, 35,  70, 105, 210;
  11, 22, 33, 66, 55, 110, 165, 330, 77, 154, 231, 462, 385, 770, 1155, 2310;
  ...
(End)
From _Peter Munn_, Jun 14 2020: (Start)
The initial terms are shown below, equated with the product of their prime factors to exhibit the lexicographic order. We start with 1, since 1 is factored as the empty product and the empty list is first in lexicographic order.
   n     a(n)
   0     1 = .
   1     2 = 2.
   2     3 = 3.
   3     6 = 3*2.
   4     5 = 5.
   5    10 = 5*2.
   6    15 = 5*3.
   7    30 = 5*3*2.
   8     7 = 7.
   9    14 = 7*2.
  10    21 = 7*3.
  11    42 = 7*3*2.
  12    35 = 7*5.
(End)

Reinhard Zumkeller, Table of n, a(n) for n = 0..8191

Row 1 of A285321.
Equivalent sequences for k-th-power-free numbers: A101278 (k=3), A101942 (k=4), A101943 (k=5), A054842 (k=10).
Cf. A007088, A030308, A000040, A013929, A005117, A103785, A103786, A110765, A064273, A246353, A283475, A283477, A285319, A285331, A285332, A288569, A293442.
Cf. A109162 (iterates).
Cf. also A048675 (a left inverse), A087207, A097248, A260443, A054841.
Cf. A285315 (numbers for which a(n) < n), A285316 (for which a(n) > n).
Cf. A276076, A276086 (analogous sequences for factorial and primorial bases), A334110 (terms squared).
For partial sums see A288570.
A003961, A003987, A004198, A059897, A089913, A331590, A334747 are used to express relationships between sequence terms.
Column 1 of A329332.
Even bisection (which contains the odd terms): A332382.
A160102 composed with A052330, and subsequence of the latter.
Related to A000079 via A225546, to A057335 via A122111, to A008578 via A336322.
Least prime index of a(n) is A001511.
Greatest prime index of a(n) is A029837 or A070939.
Taking prime indices gives A048793, reverse A272020, row sums A029931.
A112798 lists prime indices, length A001222, sum A056239.
Cf. A000120, A000720, A005940, A066099, A358137, A358170.

a019565 n = product $ zipWith (^) a000040_list (a030308_row n)
-- Reinhard Zumkeller, Apr 27 2013

a:= proc(n) local i, m, r; m:=n; r:=1;
      for i while m>0 do if irem(m,2,'m')=1
        then r:=r*ithprime(i) fi od; r
    end:
seq(a(n), n=0..60);  # Alois P. Heinz, Sep 06 2014

Do[m=1;o=1;k1=k;While[ k1>0, k2=Mod[k1, 2];If[k2\[Equal]1, m=m*Prime[o]];k1=(k1-k2)/ 2;o=o+1];Print[m], {k, 0, 55}] (* Lei Zhou, Feb 15 2005 *)
Table[Times @@ Prime@ Flatten@ Position[#, 1] &@ Reverse@ IntegerDigits[n, 2], {n, 0, 55}]  (* Michael De Vlieger, Aug 27 2016 *)
b[0] := {1}; b[n_] := Flatten[{ b[n - 1], b[n - 1] * Prime[n] }];
  a = b[6] (* Fred Daniel Kline, Jun 26 2017 *)

a(n)=factorback(vecextract(primes(logint(n+!n,2)+1),n))  \\ M. F. Hasler, Mar 26 2011, updated Aug 22 2014, updated Mar 01 2018

from operator import mul
from functools import reduce
from sympy import prime
def A019565(n):
    return reduce(mul,(prime(i+1) for i,v in enumerate(bin(n)[:1:-1]) if v == '1')) if n > 0 else 1
# Chai Wah Wu, Dec 25 2014

(define (A019565 n) (let loop ((n n) (i 1) (p 1)) (cond ((zero? n) p) ((odd? n) (loop (/ (- n 1) 2) (+ 1 i) (* p (A000040 i)))) (else (loop (/ n 2) (+ 1 i) p))))) ;; (Requires only the implementation of A000040 for prime numbers.) - Antti Karttunen, Apr 20 2017

G.f.: Product_{k>=0} (1 + prime(k+1)*x^2^k), where prime(k)=A000040(k). - Ralf Stephan, Jun 20 2003
a(n) = f(n, 1, 1) with f(x, y, z) = if x > 0 then f(floor(x/2), y*prime(z)^(x mod 2), z+1) else y. - Reinhard Zumkeller, Mar 13 2010
For all n >= 0: A048675(a(n)) = n; A013928(a(n)) = A064273(n). - Antti Karttunen, Jul 29 2015
a(n) = a(2^x)*a(2^y)*a(2^z)*... = prime(x+1)*prime(y+1)*prime(z+1)*..., where n = 2^x + 2^y + 2^z + ... - Benedict W. J. Irwin, Jul 24 2016
From Antti Karttunen, Apr 18 2017 and Jun 18 2017: (Start)
a(n) = A097248(A260443(n)), a(A005187(n)) = A283475(n), A108951(a(n)) = A283477(n).
A055396(a(n)) = A001511(n), a(A087207(n)) = A007947(n). (End)
a(2^n - 1) = A002110(n). - Michael De Vlieger, Jul 05 2017
a(n) = A225546(A000079(n)). - Peter Munn, Oct 31 2019
From Peter Munn, Mar 04 2022: (Start)
a(2n) = A003961(a(n)); a(2n+1) = 2*a(2n).
a(x XOR y) = A059897(a(x), a(y)) = A089913(a(x), a(y)), where XOR denotes bitwise exclusive OR (A003987).
a(n+1) = A334747(a(n)).
a(x+y) = A331590(a(x), a(y)).
a(n) = A336322(A008578(n+1)).
(End)

Definition corrected by Klaus-R. Löffler, Aug 20 2014

New name from Peter Munn, Jun 14 2020

A006519 Highest power of 2 dividing n.

Original entry on oeis.org

1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 32, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 64, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 32, 1, 2, 1, 4, 1, 2

Offset: 1

N. J. A. Sloane, Simon Plouffe

Least positive k such that m^k + 1 divides m^n + 1 (with fixed base m). - Vladimir Baltic, Mar 25 2002
To construct the sequence: start with 1, concatenate 1, 1 and double last term gives 1, 2. Concatenate those 2 terms, 1, 2, 1, 2 and double last term 1, 2, 1, 2 -> 1, 2, 1, 4. Concatenate those 4 terms: 1, 2, 1, 4, 1, 2, 1, 4 and double last term -> 1, 2, 1, 4, 1, 2, 1, 8, etc. - Benoit Cloitre, Dec 17 2002
a(n) = gcd(seq(binomial(2*n, 2*m+1)/2, m = 0 .. n - 1)) (odd numbered entries of even numbered rows of Pascal's triangle A007318 divided by 2), where gcd() denotes the greatest common divisor of a set of numbers. Due to the symmetry of the rows it suffices to consider m = 0 .. floor((n-1)/2). - Wolfdieter Lang, Jan 23 2004
Equals the continued fraction expansion of a constant x (cf. A100338) such that the continued fraction expansion of 2*x interleaves this sequence with 2's: contfrac(2*x) = [2; 1, 2, 2, 2, 1, 2, 4, 2, 1, 2, 2, 2, 1, 2, 8, 2, ...].
Simon Plouffe observes that this sequence and A003484 (Radon function) are very similar, the difference being all zeros except for every 16th term (see A101119 for nonzero differences). Dec 02 2004
This sequence arises when calculating the next odd number in a Collatz sequence: Next(x) = (3*x + 1) / A006519, or simply (3*x + 1) / BitAnd(3*x + 1, -3*x - 1). - Jim Caprioli, Feb 04 2005
a(n) = n if and only if n = 2^k. This sequence can be obtained by taking a(2^n) = 2^n in place of a(2^n) = n and using the same sequence building approach as in A001511. - Amarnath Murthy, Jul 08 2005
Also smallest m such that m + n - 1 = m XOR (n - 1); A086799(n) = a(n) + n - 1. - Reinhard Zumkeller, Feb 02 2007
Number of 1's between successive 0's in A159689. - Philippe Deléham, Apr 22 2009
Least number k such that all coefficients of k*E(n, x), the n-th Euler polynomial, are integers (cf. A144845). - Peter Luschny, Nov 13 2009
In the binary expansion of n, delete everything left of the rightmost 1 bit. - Ralf Stephan, Aug 22 2013
The equivalent sequence for partitions is A194446. - Omar E. Pol, Aug 22 2013
Also the 2-adic value of 1/n, n >= 1. See the Mahler reference, definition on p. 7. This is a non-archimedean valuation. See Mahler, p. 10. Sometimes called 2-adic absolute value of 1/n. - Wolfdieter Lang, Jun 28 2014
First 2^(k-1) - 1 terms are also the heights of the successive rectangles and squares of width 2 that are adjacent to any of the four sides of the toothpick structure of A139250 after 2^k stages, with k >= 2. For example: if k = 5 the heights after 32 stages are [1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1] respectively, the same as the first 15 terms of this sequence. - Omar E. Pol, Dec 29 2020

			2^3 divides 24, but 2^4 does not divide 24, so a(24) = 8.
2^0 divides 25, but 2^1 does not divide 25, so a(25) = 1.
2^1 divides 26, but 2^2 does not divide 26, so a(26) = 2.
Per _Marc LeBrun_'s 2000 comment, a(n) can also be determined with bitwise operations in two's complement. For example, given n = 48, we see that n in binary in an 8-bit byte is 00110000 while -n is 11010000. Then 00110000 AND 11010000 = 00010000, which is 16 in decimal, and therefore a(48) = 16.
G.f. = x + 2*x^2 + x^3 + 4*x^4 + x^5 + 2*x^6 + x^7 + 8*x^8 + x^9 + ...

Kurt Mahler, p-adic numbers and their functions, second ed., Cambridge University Press, 1981.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 1..10000
Dzmitry Badziahin and Jeffrey Shallit, An Unusual Continued Fraction, arXiv:1505.00667 [math.NT], 2015.
Dzmitry Badziahin and Jeffrey Shallit, An unusual continued fraction, Proc. Amer. Math. Soc. 144 (2016), 1887-1896.
Tyler Ball, Tom Edgar, and Daniel Juda, Dominance Orders, Generalized Binomial Coefficients, and Kummer's Theorem, Mathematics Magazine, Vol. 87, No. 2, April 2014, pp. 135-143.
M. Beeler, R. W. Gosper and R. Schroeppel, Item 175, in Beeler, M., Gosper, R. W. and Schroeppel, R. HAKMEM. MIT AI Memo 239, Feb 29 1972.
Ron Brown and Jonathan L. Merzel, The number of Ducci sequences with a given period, Fib. Quart., 45 (2007), 115-121.
Daniel Bruns, Wojciech Mostowski, and Mattias Ulbrich, Implementation-level verification of algorithms with KeY, International Journal on Software Tools for Technology Transfer, November 2013.
Victor Meally, Letter to N. J. A. Sloane, May 1975.
Laurent Orseau, Levi H. S. Lelis, and Tor Lattimore, Zooming Cautiously: Linear-Memory Heuristic Search With Node Expansion Guarantees, arXiv:1906.03242 [cs.AI], 2019.
Laurent Orseau, Levi H. S. Lelis, Tor Lattimore, and Théophane Weber, Single-Agent Policy Tree Search With Guarantees, arXiv:1811.10928 [cs.AI], 2018, also in Advances in Neural Information Processing Systems, 32nd Conference on Neural Information Processing Systems (NIPS 2018), Montréal, Canada.
Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions.
Ralf Stephan, Table of generating functions.
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
Eric Weisstein's World of Mathematics, Even Part.
Wikipedia, Converse nonimplication.
Index entries for sequences related to binary expansion of n.

Partial sums are in A006520, second partial sums in A022560.
Sequences used in definitions of this sequence: A000079, A001511, A004198, A007814.
Cf. A000265, A100338, A003484, A001620, A101119, A002487, A139250.
Sequences with related definitions: A038712, A171977, A135481 (GS(1, 6)).
This is Guy Steele's sequence GS(5, 2) (see A135416).
Related to A007913 via A225546.
A059897 is used to express relationship between sequence terms.
Cf. A091476 (Dgf at s=2).

import Data.Bits ((.&.))
a006519 n = n .&. (-n) :: Integer
-- Reinhard Zumkeller, Mar 11 2012, Dec 29 2011

using IntegerSequences
[EvenPart(n) for n in 1:102] |> println  # Peter Luschny, Sep 25 2021

[2^Valuation(n, 2): n in [1..100]]; // Vincenzo Librandi, Mar 27 2015

with(numtheory): for n from 1 to 200 do if n mod 2 = 1 then printf(`%d,`,1) else printf(`%d,`,2^ifactors(n)[2][1][2]) fi; od:
A006519 := proc(n) if type(n,'odd') then 1 ; else for f in ifactors(n)[2] do if op(1,f) = 2 then return 2^op(2,f) ; end if; end do: end if; end proc: # R. J. Mathar, Oct 25 2010
A006519 := n -> 2^padic[ordp](n,2): # Peter Luschny, Nov 26 2010

lowestOneBit[n_] := Block[{k = 0}, While[Mod[n, 2^k] == 0, k++]; 2^(k - 1)]; Table[lowestOneBit[n], {n, 102}] (* Robert G. Wilson v Nov 17 2004 *)
Table[2^IntegerExponent[n, 2], {n, 128}] (* Jean-François Alcover, Feb 10 2012 *)
Table[BitAnd[BitNot[i - 1], i], {i, 1, 102}] (* Peter Luschny, Oct 10 2019 *)

PARI
```
{a(n) = 2^valuation(n, 2)};
```
PARI
```
a(n)=1<Joerg Arndt, Jun 10 2011
```

a(n)=bitand(n,-n); \\ Joerg Arndt, Jun 10 2011

a(n)=direuler(p=2,n,if(p==2,1/(1-2*X),1/(1-X)))[n] \\ Ralf Stephan, Mar 27 2015

def A006519(n): return n&-n # Chai Wah Wu, Jul 06 2022

(1 to 128).map(Integer.lowestOneBit()) // _Alonso del Arte, Mar 04 2020

a(n) = n AND -n (where "AND" is bitwise, and negative numbers are represented in two's complement in a suitable bit width). - Marc LeBrun, Sep 25 2000, clarified by Alonso del Arte, Mar 16 2020
Also: a(n) = gcd(2^n, n). - Labos Elemer, Apr 22 2003
Multiplicative with a(p^e) = p^e if p = 2; 1 if p > 2. - David W. Wilson, Aug 01 2001
G.f.: Sum_{k>=0} 2^k*x^2^k/(1 - x^2^(k+1)). - Ralf Stephan, May 06 2003
Dirichlet g.f.: zeta(s)*(2^s - 1)/(2^s - 2) = zeta(s)*(1 - 2^(-s))/(1 - 2*2^(-s)). - Ralf Stephan, Jun 17 2007
a(n) = 2^floor(A002487(n - 1) / A002487(n)). - Reikku Kulon, Oct 05 2008
a(n) = 2^A007814(n). - R. J. Mathar, Oct 25 2010
a((2*k - 1)*2^e) = 2^e, k >= 1, e >= 0. - Johannes W. Meijer, Jun 07 2011
a(n) = denominator of Euler(n-1, 1). - Arkadiusz Wesolowski, Jul 12 2012
a(n) = A011782(A001511(n)). - Omar E. Pol, Sep 13 2013
a(n) = (n XOR floor(n/2)) XOR (n-1 XOR floor((n-1)/2)) = n - (n AND n-1) (where "AND" is bitwise). - Gary Detlefs, Jun 12 2014
a(n) = ((n XOR n-1)+1)/2. - Gary Detlefs, Jul 02 2014
a(n) = A171977(n)/2. - Peter Kern, Jan 04 2017
a(n) = 2^(A001511(n)-1). - Doug Bell, Jun 02 2017
a(n) = abs(A003188(n-1) - A003188(n)). - Doug Bell, Jun 02 2017
Conjecture: a(n) = (1/(A000203(2*n)/A000203(n)-2)+1)/2. - Velin Yanev, Jun 30 2017
a(n) = (n-1) o n where 'o' is the bitwise converse nonimplication. 'o' is not commutative. n o (n+1) = A135481(n). - Peter Luschny, Oct 10 2019
From Peter Munn, Dec 13 2019: (Start)
a(A225546(n)) = A225546(A007913(n)).
a(A059897(n,k)) = A059897(a(n), a(k)). (End)
Sum_{k=1..n} a(k) ~ (1/(2*log(2)))*n*log(n) + (3/4 + (gamma-1)/(2*log(2)))*n, where gamma is Euler's constant (A001620). - Amiram Eldar, Nov 15 2022
a(n) = n / A000265(n). - Amiram Eldar, May 22 2025

More terms from James Sellers, Jun 20 2000

A003987 Table of n XOR m (or Nim-sum of n and m) read by antidiagonals with m>=0, n>=0.

Original entry on oeis.org

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

Offset: 0

Marc LeBrun

Another way to construct the array: construct an infinite square matrix starting in the top left corner using the rule that each entry is the smallest nonnegative number that is not in the row to your left or in the column above you.
After a few moves the [symmetric] matrix looks like this:
  0 1 2 3 4 5 ...
  1 0 3 2 5 ...
  2 3 0 1 ?
  3 2 1
  4 5 ?
  5
The ? is then replaced with a 6.

			Table begins
   0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, ...
   1,  0,  3,  2,  5,  4,  7,  6,  9,  8, 11, 10, ...
   2,  3,  0,  1,  6,  7,  4,  5, 10, 11,  8, ...
   3,  2,  1,  0,  7,  6,  5,  4, 11, 10, ...
   4,  5,  6,  7,  0,  1,  2,  3, 12, ...
   5,  4,  7,  6,  1,  0,  3,  2, ...
   6,  7,  4,  5,  2,  3,  0, ...
   7,  6,  5,  4,  3,  2, ...
   8,  9, 10, 11, 12, ...
   9,  8, 11, 10, ...
  10, 11,  8, ...
  11, 10, ...
  12, ...
  ...
The first few antidiagonals are
   0;
   1,  1;
   2,  0,  2;
   3,  3,  3,  3;
   4,  2,  0,  2,  4;
   5,  5,  1,  1,  5,  5;
   6,  4,  6,  0,  6,  4,  6;
   7,  7,  7,  7,  7,  7,  7,  7;
   8,  6,  4,  6,  0,  6,  4,  6,  8;
   9,  9,  5,  5,  1,  1,  5,  5,  9,  9;
  10,  8, 10,  4,  2,  0,  2,  4, 10,  8, 10;
  11, 11, 11, 11,  3,  3,  3,  3, 11, 11, 11, 11;
  12, 10,  8, 10, 12,  2,  0,  2, 12, 10,  8, 10, 12;
  ...
[Symmetric] matrix in base 2:
     0    1   10   11  100  101,  110  111 1000 1001 1010 1011 ...
     1    0   11   10  101  100,  111  110 1001 1000 1011  ...
    10   11    0    1  110  111,  100  101 1010 1011  ...
    11   10    1    0  111  110,  101  100 1011  ...
   100  101  110  111    0    1    10   11  ...
   101  100  111  110    1    0    11  ...
   110  111  100  101   10   11   ...
   111  110  101  100   11  ...
  1000 1001 1010 1011  ...
  1001 1000 1011  ...
  1010 1011  ...
  1011  ...
   ...

E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways, Academic Press, NY, 2 vols., 1982, see p. 60.
J. H. Conway, On Numbers and Games. Academic Press, NY, 1976, pp. 51-53.
Eric Friedman, Scott M. Garrabrant, Ilona K. Phipps-Morgan, A. S. Landsberg and Urban Larsson, Geometric analysis of a generalized Wythoff game, in Games of no Chance 5, MSRI publ. Cambridge University Press, date?
D. Gale, Tracking the Automatic Ant and Other Mathematical Explorations, A Collection of Mathematical Entertainments Columns from The Mathematical Intelligencer, Springer, 1998; see p. 190. [From N. J. A. Sloane, Jul 14 2009]
R. K. Guy, Impartial games, pp. 35-55 of Combinatorial Games, ed. R. K. Guy, Proc. Sympos. Appl. Math., 43, Amer. Math. Soc., 1991.

T. D. Noe, Rows n = 0..100 of triangle, flattened
J.-P. Allouche and J. Shallit, The Ring of k-regular Sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
Rémy Sigrist, Colored representation of T(x,y) for x = 0..1023 and y = 0..1023 (where the hue is function of T(x,y) and black pixels correspond to zeros)
N. J. A. Sloane, My favorite integer sequences, in Sequences and their Applications (Proceedings of SETA '98).
N. J. A. Sloane, The OEIS: A Fingerprint File for Mathematics, arXiv:2105.05111 [math.HO], 2021. Mentions this sequence.
Index entries for sequences related to Nim-sums

Initial rows are A001477, A004442, A004443, A004444, etc. Cf. A051775, A051776.
Cf. A003986 (OR), A004198 (AND), A221146 (carries).
Antidiagonal sums are in A006582.

nimsum := proc(a,b) local t1,t2,t3,t4,l; t1 := convert(a+2^20,base,2); t2 := convert(b+2^20,base,2); t3 := evalm(t1+t2); map(x->x mod 2, t3); t4 := convert(evalm(%),list); l := convert(t4,base,2,10); sum(l[k]*10^(k-1), k=1..nops(l)); end; # memo: adjust 2^20 to be much bigger than a and b
AT := array(0..N,0..N); for a from 0 to N do for b from a to N do AT[a,b] := nimsum(a,b); AT[b,a] := AT[a,b]; od: od:
# alternative:
read("transforms") :
A003987 := proc(n,m)
    XORnos(n,m) ;
end proc: # R. J. Mathar, Apr 17 2013
seq(seq(Bits:-Xor(k,m-k),k=0..m),m=0..20); # Robert Israel, Dec 31 2015

Flatten[Table[BitXor[b, a - b], {a, 0, 10}, {b, 0, a}]] (* BitXor and Nim Sum are equivalent *)

tabl(nn) = {for(n=0, nn, for(k=0, n, print1(bitxor(k, n - k),", ");); print(););};
tabl(13) \\ Indranil Ghosh, Mar 31 2017

for n in range(14):
    print([k^(n - k) for k in range(n + 1)]) # Indranil Ghosh, Mar 31 2017

T(2i,2j) = 2T(i,j), T(2i+1,2j) = 2T(i,j) + 1.

A003986 Table T(n,k) = n OR k read by antidiagonals.

Original entry on oeis.org

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

Offset: 0

Marc LeBrun

			The upper left corner of the array starts in row x=0 with columns y>=0 as:
   0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, ...
   1,  1,  3,  3,  5,  5,  7,  7,  9,  9, 11, 11, 13, ...
   2,  3,  2,  3,  6,  7,  6,  7, 10, 11, 10, 11, 14, ...
   3,  3,  3,  3,  7,  7,  7,  7, 11, 11, 11, 11, 15, ...
   4,  5,  6,  7,  4,  5,  6,  7, 12, 13, 14, 15, 12, ...
   5,  5,  7,  7,  5,  5,  7,  7, 13, 13, 15, 15, 13, ...
   6,  7,  6,  7,  6,  7,  6,  7, 14, 15, 14, 15, 14, ...
   7,  7,  7,  7,  7,  7,  7,  7, 15, 15, 15, 15, 15, ...
   8,  9, 10, 11, 12, 13, 14, 15,  8,  9, 10, 11, 12, ...
   9,  9, 11, 11, 13, 13, 15, 15,  9,  9, 11, 11, 13, ...
  10, 11, 10, 11, 14, 15, 14, 15, 10, 11, 10, 11, 14, ...

T. D. Noe, Rows n=0..100 of triangle, flattened

Cf. A003987 (XOR) and A004198 (AND). Cf. also A075173, A075175.

Antidiagonal sums are in A006583.

#include 
int main()
{
int n, k;
for (n=0; n<=20; n++){
    for(k=0; k<=n; k++){
        printf("%d, ", (k|(n - k)));
    }
    printf("\n");
}
return 0;
} /* Indranil Ghosh, Apr 01 2017 */

import Data.Bits ((.|.))
a003986 n k = (n - k) .|. k :: Int
a003986_row n = map (a003986 n) [0..n]
a003986_tabl = map a003986_row [0..]
-- Reinhard Zumkeller, Aug 05 2014

read("transforms") ;
A003986 := proc(x,y) ORnos(x,y) ;end proc:
for d from 0 to 12 do for x from 0 to d do printf("%d,", A003986(x,d-x)) ; end do: end do: # R. J. Mathar, May 28 2011

Table[BitOr[k, n - k], {n, 0, 20}, {k, 0, n}] //Flatten (* Indranil Ghosh, Apr 01 2017 *)

tabl(nn) = {for(n=0, nn, for(k=0, n, print1(bitor(k, n - k), ", "); ); print(); ); };
tabl(20) \\ Indranil Ghosh, Apr 01 2017

for n in range(21):
    print([k|(n - k) for k in range(n + 1)])
# Indranil Ghosh, Apr 01 2017

T(x,y) = T(y,x) = A080098(x,y). - R. J. Mathar, May 28 2011

Name edited by Michel Marcus, Jan 17 2023

A003989 Triangle T from the array A(x, y) = gcd(x,y), for x >= 1, y >= 1, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 4, 1, 2, 1, 1, 1, 3, 1, 1, 3, 1, 1, 1, 2, 1, 2, 5, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 1, 6, 1, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 7, 2, 1, 2, 1, 2, 1, 1, 1, 3, 1, 5, 3, 1, 1, 3, 5, 1, 3, 1, 1, 1, 2, 1

Offset: 1

Marc LeBrun

For m < n, the maximal number of nonattacking queens that can be placed on the n by m rectangular toroidal chessboard is gcd(m,n), except in the case m=3, n=6.
The determinant of the matrix of the first n rows and columns is A001088(n). [Smith, Mansion] - Michael Somos, Jun 25 2012
Imagine a torus having regular polygonal cross-section of m sides. Now, break the torus and twist the free ends, preserving rotational symmetry, then reattach the ends. Let n be the number of faces passed in twisting the torus before reattaching it. For example, if n = m, then the torus has exactly one full twist. Do this for arbitrary m and n (m > 1, n > 0). Now, count the independent, closed paths on the surface of the resulting torus, where a path is "closed" if and only if it returns to its starting point after a finite number of times around the surface of the torus. Conjecture: this number is always gcd(m,n). NOTE: This figure constitutes a group with m and n the binary arguments and gcd(m,n) the resulting value. Twisting in the reverse direction is the inverse operation, and breaking & reattaching in place is the identity operation. - Jason Richardson-White, May 06 2013
Regarded as a triangle, table of gcd(n - k +1, k) for 1 <= k <= n. - Franklin T. Adams-Watters, Oct 09 2014
The n-th row of the triangle is 1,...,1, if and only if, n + 1 is prime. - Alexandra Hercilia Pereira Silva, Oct 03 2020

			The array A begins:
  [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
  [1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2]
  [1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1]
  [1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4]
  [1, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1]
  [1, 2, 3, 2, 1, 6, 1, 2, 3, 2, 1, 6, 1, 2, 3, 2]
  [1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 7, 1, 1]
  [1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 8]
  [1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, 1, 3, 1]
  [1, 2, 1, 2, 5, 2, 1, 2, 1, 10, 1, 2, 1, 2, 5, 2]
  [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11, 1, 1, 1, 1, 1]
  [1, 2, 3, 4, 1, 6, 1, 4, 3, 2, 1, 12, 1, 2, 3, 4]
  ...
The triangle T begins:
  n\k 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 ...
  1:  1
  2:  1  1
  3:  1  2  1
  4:  1  1  1  1
  5:  1  2  3  2  1
  6:  1  1  1  1  1  1
  7:  1  2  1  4  1  2  1
  8:  1  1  3  1  1  3  1  1
  9:  1  2  1  2  5  2  1  2  1
 10:  1  1  1  1  1  1  1  1  1  1
 11:  1  2  3  4  1  6  1  4  3  2  1
 12:  1  1  1  1  1  1  1  1  1  1  1  1
 13:  1  2  1  2  1  2  7  2  1  2  1  2  1
 14:  1  1  3  1  5  3  1  1  3  5  1  3  1  1
 15:  1  2  1  4  1  2  1  8  1  2  1  4  1  2  1
 ...  - _Wolfdieter Lang_, May 12 2018

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, 2nd ed., 1994, ch. 4.
D. E. Knuth, The Art of Computer Programming, Addison-Wesley, section 4.5.2.

T. D. Noe, First 100 antidiagonals of array, flattened
Grant Cairns, Queens on Non-square Tori, El. J. Combinatorics, N6, 2001.
Marc Chamberland, Factored matrices can generate combinatorial identities, Linear Algebra and its Applications, Volume 438, Issue 4, 2013, pp. 1667-1677.
Warren P. Johnson, An LDU Factorization in Elementary Number Theory, Mathematics Magazine, Vol. 76, No. 5 (Dec., 2003), pp. 392-394.
P. Mansion, On an Arithmetical Theorem of Professor Smith's, Messenger of Mathematics, (1878), pp. 81-82.
Kival Ngaokrajang, Pattern of GCD(x,y) > 1 for x and y = 1..60. Non-isolated values larger than 1 (polyomino shapes) are colored.
Marcelo Polezzi, A Geometrical Method for Finding an Explicit Formula for the Greatest Common Divisor, The American Mathematical Monthly, Vol. 104, No. 5 (May, 1997), pp. 445-446.
Mihai Prunescu and Joseph Shunia, Arithmetic-term representations for the greatest common divisor, arXiv:2411.06430 [math.NT], 2024.
H. J. S. Smith, On the value of a certain arithmetical determinant, Proc. London Math. Soc. 7 (1875-1876), pp. 208-212.
Index entries for sequences related to lcm's

Rows, columns and diagonals: A089128, A109007, A109008, A109009, A109010, A109011, A109012, A109013, A109014, A109015.
A109004 is (0, 0) based.
Cf.  A001088, A003990, A003991, A050873, A051731, A054431, A054522.
Cf. also A091255 for GF(2)[X] polynomial analog.
A(x, y) = A075174(A004198(A075173(x), A075173(y))) = A075176(A004198(A075175(x), A075175(y))).
Antidiagonal sums are in A006579.

Flat(List([1..15],n->List([1..n],k->Gcd(n-k+1,k)))); # Muniru A Asiru, Aug 26 2018

a:=(n,k)->gcd(n-k+1,k): seq(seq(a(n,k),k=1..n),n=1..15); # Muniru A Asiru, Aug 26 2018

Table[ GCD[x - y + 1, y], {x, 1, 15}, {y, 1, x}] // Flatten (* Jean-François Alcover, Dec 12 2012 *)

{A(n, m) = gcd(n, m)}; /* Michael Somos, Jun 25 2012 */

Multiplicative in both parameters with a(p^e, m) = gcd(p^e, m). - David W. Wilson, Jun 12 2005
T(n, k) = A(n - k + 1, k) = gcd(n - k + 1, k), n >= 1, k = 1..n. See a comment above and the Mathematica program. - Wolfdieter Lang, May 12 2018
Dirichlet generating function: Sum_{n>=1} Sum_{k>=1} gcd(n, k)/n^s/k^c = zeta(s)*zeta(c)*zeta(s + c - 1)/zeta(s + c). - Mats Granvik, Feb 13 2021
The LU decomposition of this square array = A051731 * transpose(A054522) (see Johnson (2003) or Chamberland (2013), p. 1673). - Peter Bala, Oct 15 2023

A046644 From square root of Riemann zeta function: form Dirichlet series Sum b_n/n^s whose square is zeta function; sequence gives denominator of b_n.

Original entry on oeis.org

1, 2, 2, 8, 2, 4, 2, 16, 8, 4, 2, 16, 2, 4, 4, 128, 2, 16, 2, 16, 4, 4, 2, 32, 8, 4, 16, 16, 2, 8, 2, 256, 4, 4, 4, 64, 2, 4, 4, 32, 2, 8, 2, 16, 16, 4, 2, 256, 8, 16, 4, 16, 2, 32, 4, 32, 4, 4, 2, 32, 2, 4, 16, 1024, 4, 8, 2, 16, 4, 8, 2, 128, 2, 4, 16, 16, 4, 8

Offset: 1

N. J. A. Sloane

From Antti Karttunen, Aug 21 2018: (Start)

a(n) is the denominator of any rational-valued sequence f(n) which has been defined as f(n) = (1/2) * (b(n) - Sum_{d|n, d>1, d

Proof:

Proof is by induction. We assume as our induction hypothesis that the given multiplicative formula for A046644 (resp. additive formula for A046645) holds for all proper divisors d|n, dA046645(p) = 1. [Remark: for squares of primes, f(p^2) = (4*b(p^2) - 1)/8, thus a(p^2) = 8.]

First we note that A005187(x+y) <= A005187(x) + A005187(y), with equivalence attained only when A004198(x,y) = 0, that is, when x and y do not have any 1-bits in the shared positions. Let m = Sum_{e} A005187(e), with e ranging over the exponents in prime factorization of n.

For [case A] any n in A268388 it happens that only when d (and thus also n/d) are infinitary divisors of n will Sum_{e} A005187(e) [where e now ranges over the union of multisets of exponents in the prime factorizations of d and n/d] attain value m, which is the maximum possible for such sums computed for all divisor pairs d and n/d. For any n in A268388, A037445(n) = 2^k, k >= 2, thus A037445(n) - 2 = 2 mod 4 (excluding 1 and n from the count, thus -2). Thus, in the recursive formula above, the maximal denominator that occurs in the sum is 2^m which occurs k times, with k being an even number, but not a multiple of 4, thus the factor (1/2) in the front of the whole sum will ensure that the denominator of the whole expression is 2^m [which thus is equal to 2^A046645(n) = a(n)].

On the other hand [case B], for squares in A050376 (A082522, numbers of the form p^(2^k) with p prime and k>0), all the sums A005187(x)+A005187(y), where x+y = 2^k, 0 < x <= y < 2^k are less than A005187(2^k), thus it is the lonely "middle pair" f(p^(2^(k-1))) * f(p^(2^(k-1))) among all the pairs f(d)*f(n/d), 1 < d < n = p^(2^k) which yields the maximal denominator. Furthermore, as it occurs an odd number of times (only once), the common factor (1/2) for the whole sum will increase the exponent of 2 in denominator by one, which will be (2*A005187(2^(k-1))) + 1 = A005187(2^k) = A046645(p^(2^k)).

(End)

From Antti Karttunen, Aug 21 2018: (Start)

The following list gives a few such pairs num(n), b(n) for which b(n) is Dirichlet convolution of num(n)/a(n). Here ε stands for sequence A063524 (1, 0, 0, ...).

Numerators Dirichlet convolution of numerator(n)/a(n) yields

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

A046643 A000012

A257098 A008683

A317935 A003557

A318321 A003961

A317830 A175851

A317833 A078898

A317834 A078899

A317847 A303757

A317835 ε + A003415

A317845 ε + A001065

A317846 ε + A051953

A317936 ε + A100995

A317937 ε + A001221

A317938 ε + A001222

A317939 ε + A010051 (= A080339)

(End)

This sequence gives an upper bound for the denominators of any rational-valued sequence obtained as the "Dirichlet Square Root" of any integer-valued sequence. - Andrew Howroyd, Aug 23 2018

Antti Karttunen, Table of n, a(n) for n = 1..8192
Wikipedia, Dirichlet convolution
Index entries for sequences computed from exponents in factorization of n

Cf. A000079, A005187, A028234, A037445, A050376, A067029, A082522, A268388.
See A046643 for more details. See also A046645, A317940.
Cf. A299150, A299152, A317832, A317926, A317932, A317934 (for denominator sequences of other similar constructions).

b[1] = 1; b[n_] := b[n] = (dn = Divisors[n]; c = 1;
Do[c = c - b[dn[[i]]]*b[n/dn[[i]]], {i, 2, Length[dn] - 1}]; c/2); a[n_] := Denominator[b[n]]; a /@ Range[78] (* Jean-François Alcover, Apr 04 2011, after Maple code in A046643 *)
a18804[n_] := Sum[n EulerPhi[d]/d, {d, Divisors[n]}];
f[1] = 1; f[n_] := f[n] = 1/2 (a18804[n] - Sum[f[d] f[n/d], {d, Divisors[ n][[2 ;; -2]]}]);
a[n_] := f[n] // Denominator;
Array[a, 78] (* Jean-François Alcover, Sep 13 2018, after A318443 *)

A046643perA046644(n) = { my(c=1); if(1==n,c,fordiv(n,d, if((d>1)&&(dA046643perA046644(d)*A046643perA046644(n/d)))); (c/2)); }
A046644(n) = denominator(A046643perA046644(n)); \\ After the Maple-program given in A046643, Antti Karttunen, Jul 08 2017

A005187(n) = { my(s=n); while(n>>=1, s+=n); s; };
A046644(n) = factorback(apply(e -> 2^A005187(e),factor(n)[,2])); \\ Antti Karttunen, Aug 12 2018

for(n=1, 100, print1(denominator(direuler(p=2, n, 1/(1-X)^(1/2))[n]), ", ")) \\ Vaclav Kotesovec, May 04 2025

;; With memoization-macro definec.
(definec (A046644 n) (if (= 1 n) n (* (A000079 (A005187 (A067029 n))) (A046644 (A028234 n))))) ;; Antti Karttunen, Jul 08 2017

From Antti Karttunen, Jul 08 2017: (Start)
Multiplicative with a(p^n) = 2^A005187(n).
a(1) = 1; for n > 1, a(n) = A000079(A005187(A067029(n))) * a(A028234(n)).
a(n) = A000079(A046645(n)).
(End)
Sum_{j=1..n} A046643(j)/A046644(j) ~ n / sqrt(Pi*log(n)) * (1 + (1 - gamma/2)/(2*log(n))), where gamma is the Euler-Mascheroni constant A001620. - Vaclav Kotesovec, May 04 2025

A057300 Binary counter with odd/even bit positions swapped; base-4 counter with 1's replaced by 2's and vice versa.

Original entry on oeis.org

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

Offset: 0

Marc LeBrun, Aug 24 2000

A self-inverse permutation of the integers.
a(n) = n if and only if n can be written as 3*Sum_{k>=0} d_i*4^k, where d_i is either 0 or 1. - Jon Perry, Oct 06 2012
From Veselin Jungic, Mar 03 2015: (Start)
In 1988 A. F. Sidorenko, see the Sidorenko reference, used this sequence as an example of a permutation of the set of positive integers with the property that if positive integers i, j, and k form a 3-term arithmetic progression then the corresponding terms a(i), a(j), and a(k) do not form an arithmetic progression.
In the terminology introduced in the Brown, Jungic, and Poelstra reference, the sequence does not contain "double 3-term arithmetic progressions".
It is not difficult to check that this sequence is with unbounded gaps, i.e., for any positive number m there is a natural number n such that a(n+1) - a(n) > m.
It is an open question if every sequence of integers with bounded gaps must contain a double 3-term arithmetic progression. This problem is equivalent to the well known additive square problem in infinite words: Is it true that any infinite word with a finite set of integers as its alphabet contains two consecutive blocks of the same length and the same sum? For more details about the additive square problem in infinite words see the following references: Ardal, et al.; Brown and Freedman; Freedman; Grytczuk; Halbeisen and Hungerbuhler, and Pirillo and Varricchio.
The sequence was attributed to Sidorenko in P. Hegarty's paper "Permutations avoiding arithmetic patterns". In his paper Hegarty characterized the countably infinite abelian groups for which there exists a bijection mapping arithmetic progressions to non-arithmetic progressions. This was further generalized by Jungic and Sahasrabudhe. (End)

			a(31) = a(4*7+3) = 4*a(7) + a(3) = 4*11 + 3 = 47.

Paul Tek, Table of n, a(n) for n = 0..16383
H. Ardal, T. Brown, V. Jungic, and J. Sahasrabudhe, On Additive and Abelian Complexity in Infinite Words, INTEGERS: Elect. J. Combin. Number Theory, 12 (2012), A21.
T. C. Brown and A. R. Freedman, Arithmetic progressions in lacunary sets, Rocky Mountain J. Math., 17 Number 3 (1987), 587-596. doi:10.1216/RMJ-1987-17-3-587
T. Brown, V. Jungic, and A. Poelstra, On 3-term double arithmetic progressions, INTEGERS: Elect. J. Combin. Number Theory, 14 (2014), A43.
A. R. Freedman, Sequences on sets of four numbers, INTEGERS: Elect. J. Combin. Number Theory, 16 (2016), A33.
J. Grytczuk, Thue type problems for graphs, points and numbers, Discrete Math., 308 (2008), 4419-4429.
L. Halbeisen and N. Hungerbuhler, An application of van der Waerden's theorem in additive number theory, INTEGERS: Elect. J. Combin. Number Theory, 0 (2000), A7.
Peter Hegarty, Permutations avoiding arithmetic patterns, The Electronic Journal of Combinatorics, 11 (2004), #R39.
V. Jungic and J. Sahasrabudhe, Permutations destroying arithmetic structure, The Electronic Journal of Combinatorics, Volume 22, Issue 2 (2015), Paper #P2.5.
G. Pirillo and S. Varricchio, On uniformly repetitive semigroups, Semigroup Forum, 49 (1994), 125-129.
A. F. Sidorenko, An infinite permutation without arithmetic progressions, Discrete Math., 69 (1988), 211.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Index entries for sequences related to binary expansion of n
Index entries for sequences that are permutations of the natural numbers

Sequences used in definitions of this sequence: A000695, A059905, A059906.
Sequences with similar definitions: A057301, A126006, A126007, A126008, A163241, A163327.
A003986, A003987, A004198, A053985, A054240 are used to express relationships between sequence terms.

#include 
uint32_t a(uint32_t n) { return ((n & 0x55555555) << 1) | ((n & 0xaaaaaaaa) >> 1); } /* Falk Hüffner, Jan 23 2022 */

a:= proc(n) option remember; `if`(n=0, 0,
      a(iquo(n, 4, 'r'))*4+[0, 2, 1, 3][r+1])
    end:
seq(a(n), n=0..69);  # Alois P. Heinz, Jan 25 2022

Table[FromDigits[IntegerDigits[n,4]/.{1->2,2->1},4],{n,0,70}] (* Harvey P. Dale, Aug 24 2017 *)

A057300(n) = { my(t=1,s=0); while(n>0, if(1==(n%4),n++,if(2==(n%4),n--)); s += (n%4)*t; n >>= 2; t <<= 2); (s); }; \\ Antti Karttunen, Apr 14 2018

Conjecture: a(2*n) = -2*a(n) + 5*n, a(2*n+1) = -2*a(n) + 5*n + 2. - Ralf Stephan, Oct 11 2003
a(4n+k) = 4a(n) + a(k), 0 <= k <= 3. - Jon Perry, Oct 06 2012
a(n) = A000695(A059906(n)) + 2*A000695(A059905(n)). - Antti Karttunen, Apr 14 2018
From Peter Munn, Dec 10 2019: (Start)
a(a(n)) = n.
a(A000695(m) + 2*A000695(n)) = 2*A000695(m) + A000695(n).
a(n OR k) = a(n) OR a(k), where OR is bitwise-or (A003986).
a(n XOR k) = a(n) XOR a(k), where XOR is bitwise exclusive-or (A003987).
a(n AND k) = a(n) AND a(k), where AND is bitwise-and (A004198).
a(A054240(n,k)) = A054240(a(n), a(k)). (End)
a(n) = 5*n/4 - 3*A053985(2*n)/8. - Alan Michael Gómez Calderón, May 20 2025

A331590 Square array A(n,k) = A225546(A225546(n) * A225546(k)), n >= 1, k >= 1, read by descending antidiagonals.

Original entry on oeis.org

1, 2, 2, 3, 3, 3, 4, 6, 6, 4, 5, 8, 5, 8, 5, 6, 10, 12, 12, 10, 6, 7, 5, 15, 9, 15, 5, 7, 8, 14, 10, 20, 20, 10, 14, 8, 9, 12, 21, 24, 7, 24, 21, 12, 9, 10, 18, 24, 28, 30, 30, 28, 24, 18, 10, 11, 15, 27, 18, 35, 15, 35, 18, 27, 15, 11, 12, 22, 30, 36, 40, 42, 42, 40, 36, 30, 22, 12, 13, 24, 33, 40, 45, 20, 11, 20, 45, 40, 33, 24, 13

Offset: 1

Peter Munn, Jan 21 2020

As a binary operation, this sequence defines a commutative monoid over the positive integers that is isomorphic to multiplication. The self-inverse permutation A225546(.) provides an isomorphism. This monoid therefore has unique factorization. Its primes are the even terms of A050376: 2, 4, 16, 256, ..., which in standard integer multiplication are the powers of 2 with powers of 2 as exponents.
In this monoid, in contrast, the powers of 2 run through the squarefree numbers, the k-th power of 2 being A019565(k). 4 is irreducible and its powers are the squares of the squarefree numbers, the k-th power of 4 being A019565(k)^2 (where "^2" denotes standard integer squaring); and so on with powers of 16, 256, ...
In many cases the product of two numbers is the same here as in standard integer multiplication. See the formula section for details.

			From _Antti Karttunen_, Feb 02 2020: (Start)
The top left 16 X 16 corner of the array:
   1,  2,  3,  4,  5,  6,   7,   8,   9,  10,  11,  12,  13,  14,  15,  16, ...
   2,  3,  6,  8, 10,  5,  14,  12,  18,  15,  22,  24,  26,  21,  30,  32, ...
   3,  6,  5, 12, 15, 10,  21,  24,  27,  30,  33,  20,  39,  42,   7,  48, ...
   4,  8, 12,  9, 20, 24,  28,  18,  36,  40,  44,  27,  52,  56,  60,  64, ...
   5, 10, 15, 20,  7, 30,  35,  40,  45,  14,  55,  60,  65,  70,  21,  80, ...
   6,  5, 10, 24, 30, 15,  42,  20,  54,   7,  66,  40,  78,  35,  14,  96, ...
   7, 14, 21, 28, 35, 42,  11,  56,  63,  70,  77,  84,  91,  22, 105, 112, ...
   8, 12, 24, 18, 40, 20,  56,  27,  72,  60,  88,  54, 104,  84, 120, 128, ...
   9, 18, 27, 36, 45, 54,  63,  72,  25,  90,  99, 108, 117, 126, 135, 144, ...
  10, 15, 30, 40, 14,  7,  70,  60,  90,  21, 110, 120, 130, 105,  42, 160, ...
  11, 22, 33, 44, 55, 66,  77,  88,  99, 110,  13, 132, 143, 154, 165, 176, ...
  12, 24, 20, 27, 60, 40,  84,  54, 108, 120, 132,  45, 156, 168,  28, 192, ...
  13, 26, 39, 52, 65, 78,  91, 104, 117, 130, 143, 156,  17, 182, 195, 208, ...
  14, 21, 42, 56, 70, 35,  22,  84, 126, 105, 154, 168, 182,  33, 210, 224, ...
  15, 30,  7, 60, 21, 14, 105, 120, 135,  42, 165,  28, 195, 210,  35, 240, ...
  16, 32, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192, 208, 224, 240,  81, ...
(End)

Antti Karttunen, Antidiagonals n = 1..144, flattened
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..80200; (antidiagonals n = 1..400)
Eric Weisstein's World of Mathematics, Monoid

Isomorphic to A003991 with A225546 as isomorphism.
Cf. A003961(main diagonal), A048675, A059895, A059896, A059897.
Rows/columns, sorted in ascending order: 2: A000037, 3: A028983, 4: A252849.
A019565 lists powers of 2 in order of increasing exponent.
Powers of k, sorted in ascending order: k=2: A005117, k=3: A056911, k=4: A062503, k=5: A276378, k=6: intersection of A325698 and A005117, k=7: intersection of A007775 and A005117, k=8: A062838.
Irreducibles are A001146 (even terms of A050376).

up_to = 1275;
A019565(n) = factorback(vecextract(primes(logint(n+!n, 2)+1), n));
A048675(n) = { my(f = factor(n)); sum(k=1, #f~, f[k, 2]*2^primepi(f[k, 1]))/2; };
A331590sq(x,y) = if(1==x,y,if(1==y,x, my(fx=factor(x),fy=factor(y),u=max(#binary(vecmax(fx[, 2])),#binary(vecmax(fy[, 2]))),prodsx=vector(u,x,1),m=1); for(i=1,u,for(k=1,#fx~, if(bitand(fx[k,2],m),prodsx[i] *= fx[k,1])); for(k=1,#fy~, if(bitand(fy[k,2],m),prodsx[i] *= fy[k,1])); m<<=1); prod(i=1,u,A019565(A048675(prodsx[i]))^(1<<(i-1)))));
A331590list(up_to) = { my(v = vector(up_to), i=0); for(a=1,oo, for(col=1,a, i++; if(i > up_to, return(v)); v[i] = A331590sq(col,(a-(col-1))))); (v); };
v331590 = A331590list(up_to);
A331590(n) = v331590[n]; \\ Antti Karttunen, Feb 02 2020

Alternative definition: A(n,1) = n; A(n,k) = A(A059897(n,k), A003961(A059895(n,k))).
Main derived identities: (Start)
A(n,k) = A(k,n).
A(1,n) = n.
A(n, A(m,k)) = A(A(n,m), k).
A(m,m) = A003961(m).
A(n^2, k^2) = A(n,k)^2.
A(A003961(n), A003961(k)) = A003961(A(n,k)).
A(A019565(n), A019565(k)) = A019565(n+k).
(End)
Characterization of conditions for A(n,k) = n * k: (Start)
The following 4 conditions are equivalent:
(1) A(n,k) = n * k;
(2) A(n,k) = A059897(n,k);
(3) A(n,k) = A059896(n,k);
(4) A059895(n,k) = 1.
If gcd(n,k) = 1, A(n,k) = n * k.
If gcd(n,k) = 1, A(A225546(n), A225546(k)) = A225546(n) * A225546(k).
The previous formula implies A(n,k) = n * k in the following cases:
(1) for n = A005117(m), k = j^2;
(2) more generally for n = A005117(m_1)^(2^i_1), k = A005117(m_2)^(2^i_2), with A004198(i_1, i_2) = 0.
(End)

Previous Showing 21-30 of 96 results. Next

cp's OEIS Frontend

A324639 Numbers k such that bitand(2k,sigma(k)) = 2*bitand(k,sigma(k)-k), where bitand is bitwise-AND, A004198.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A325318 a(n) = A048250(n) AND A162296(n), where AND is the bitwise-AND, A004198.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A019565 The squarefree numbers ordered lexicographically by their prime factorization (with factors written in decreasing order). a(n) = Product_{k in I} prime(k+1), where I is the set of indices of nonzero binary digits in n = Sum_{k in I} 2^k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Scheme

Formula

Extensions

A006519 Highest power of 2 dividing n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Julia

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

Python

Scala

Formula

Extensions

A003987 Table of n XOR m (or Nim-sum of n and m) read by antidiagonals with m>=0, n>=0.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A003986 Table T(n,k) = n OR k read by antidiagonals.

Views

Author

Keywords