The OEIS is supported by the many generous donors to the OEIS Foundation.
%I M2222 N0881 #394 Feb 16 2025 08:32:20
%S 1,1,3,1,5,3,7,1,9,5,11,3,13,7,15,1,17,9,19,5,21,11,23,3,25,13,27,7,
%T 29,15,31,1,33,17,35,9,37,19,39,5,41,21,43,11,45,23,47,3,49,25,51,13,
%U 53,27,55,7,57,29,59,15,61,31,63,1,65,33,67,17,69,35,71,9,73,37,75,19,77
%N Remove all factors of 2 from n; or largest odd divisor of n; or odd part of n.
%C When n > 0 is written as k*2^j with k odd then k = A000265(n) and j = A007814(n), so: when n is written as k*2^j - 1 with k odd then k = A000265(n+1) and j = A007814(n+1), when n > 1 is written as k*2^j + 1 with k odd then k = A000265(n-1) and j = A007814(n-1).
%C Also denominator of 2^n/n (numerator is A075101(n)). - _Reinhard Zumkeller_, Sep 01 2002
%C Slope of line connecting (o, a(o)) where o = (2^k)(n-1) + 1 is 2^k and (by design) starts at (1, 1). - Josh Locker (joshlocker(AT)macfora.com), Apr 17 2004
%C Numerator of n/2^(n-1). - _Alexander Adamchuk_, Feb 11 2005
%C From _Marco Matosic_, Jun 29 2005: (Start)
%C "The sequence can be arranged in a table:
%C 1
%C 1 3 1
%C 1 5 3 7 1
%C 1 9 5 11 3 13 7 15 1
%C 1 17 9 19 5 21 11 23 3 25 13 27 7 29 15 31 1
%C Every new row is the previous row interspaced with the continuation of the odd numbers.
%C Except for the ones; the terms (t) in each column are t+t+/-s = t_+1. Starting from the center column of threes and working to the left the values of s are given by A000265 and working to the right by A000265." (End)
%C This is a fractal sequence. The odd-numbered elements give the odd natural numbers. If these elements are removed, the original sequence is recovered. - _Kerry Mitchell_, Dec 07 2005
%C 2k + 1 is the k-th and largest of the subsequence of k terms separating two successive equal entries in a(n). - _Lekraj Beedassy_, Dec 30 2005
%C It's not difficult to show that the sum of the first 2^n terms is (4^n + 2)/3. - _Nick Hobson_, Jan 14 2005
%C In the table, for each row, (sum of terms between 3 and 1) - (sum of terms between 1 and 3) = A020988. - _Eric Desbiaux_, May 27 2009
%C This sequence appears in the analysis of A160469 and A156769, which resemble the numerator and denominator of the Taylor series for tan(x). - _Johannes W. Meijer_, May 24 2009
%C Indices n such that a(n) divides 2^n - 1 are listed in A068563. - _Max Alekseyev_, Aug 25 2013
%C From _Alexander R. Povolotsky_, Dec 17 2014: (Start)
%C With regard to the tabular presentation described in the comment by Marco Matosic: in his drawing, starting with the 3rd row, the first term in the row, which is equal to 1 (or, alternatively the last term in the row, which is also equal to 1), is not in the actual sequence and is added to the drawing as a fictitious term (for the sake of symmetry); an actual A000265(n) could be considered to be a(j,k) (where j >= 1 is the row number and k>=1 is the column subscript), such that a(j,1) = 1:
%C 1
%C 1 3
%C 1 5 3 7
%C 1 9 5 11 3 13 7 15
%C 1 17 9 19 5 21 11 23 3 25 13 27 7 29 15 31
%C and so on ... .
%C The relationship between k and j for each row is 1 <= k <= 2^(j-1). In this corrected tabular representation, Marco's notion that "every new row is the previous row interspaced with the continuation of the odd numbers" remains true. (End)
%C Partitions natural numbers to the same equivalence classes as A064989. That is, for all i, j: a(i) = a(j) <=> A064989(i) = A064989(j). There are dozens of other such sequences (like A003602) for which this also holds: In general, all sequences for which a(2n) = a(n) and the odd bisection is injective. - _Antti Karttunen_, Apr 15 2017
%C From _Paul Curtz_, Feb 19 2019: (Start)
%C This sequence is the truncated triangle:
%C 1, 1;
%C 3, 1, 5;
%C 3, 7, 1, 9;
%C 5, 11, 3, 13, 7;
%C 15, 1, 17, 9, 19, 5;
%C 21, 11, 23, 3, 25, 13, 27;
%C 7, 29, 15, 31, 1, 33, 17, 35;
%C ...
%C The first column is A069834. The second column is A213671. The main diagonal is A236999. The first upper diagonal is A125650 without 0.
%C c(n) = ((n*(n+1)/2))/A069834 = 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 2, 2, 1, 1, 8, 8, 1, 1, ... for n > 0. n*(n+1)/2 is the rank of A069834. (End)
%C As well as being multiplicative, a(n) is a strong divisibility sequence, that is, gcd(a(n),a(m)) = a(gcd(n,m)) for n, m >= 1. In particular, a(n) is a divisibility sequence: if n divides m then a(n) divides a(m). - _Peter Bala_, Feb 27 2019
%C a(n) is also the map n -> A026741(n) applied at least A007814(n) times. - _Federico Provvedi_, Dec 14 2021
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Daniel Forgues, <a href="/A000265/b000265.txt">Table of n, a(n) for n = 1..100000</a> (first 10000 terms from T. D. Noe)
%H Peter Bala, <a href="/A306367/a306367.pdf">A note on the sequence of numerators of a rational function </a>
%H V. Daiev and J. L. Brown, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/6-1/advanced6-1.pdf">Problem H-81</a>, Fib. Quart., 6 (1968), 52.
%H Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>
%H Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>
%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/OddPart.html">Odd Part</a>
%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/TrigonometryAngles.html">Trigonometry Angles</a>
%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/SphereLinePicking.html">Sphere Line Picking</a>
%F a(n) = if n is odd then n, otherwise a(n/2). - _Reinhard Zumkeller_, Sep 01 2002
%F a(n) = n/A006519(n) = 2*A025480(n-1) + 1.
%F Multiplicative with a(p^e) = 1 if p = 2, p^e if p > 2. - _David W. Wilson_, Aug 01 2001
%F a(n) = Sum_{d divides n and d is odd} phi(d). - _Vladeta Jovovic_, Dec 04 2002
%F G.f.: -x/(1 - x) + Sum_{k>=0} (2*x^(2^k)/(1 - 2*x^(2^(k+1)) + x^(2^(k+2)))). - _Ralf Stephan_, Sep 05 2003
%F (a(k), a(2k), a(3k), ...) = a(k)*(a(1), a(2), a(3), ...) In general, a(n*m) = a(n)*a(m). - Josh Locker (jlocker(AT)mail.rochester.edu), Oct 04 2005
%F a(n) = Sum_{k=0..n} A127793(n,k)*floor((k+2)/2) (conjecture). - _Paul Barry_, Jan 29 2007
%F Dirichlet g.f.: zeta(s-1)*(2^s - 2)/(2^s - 1). - _Ralf Stephan_, Jun 18 2007
%F a(A132739(n)) = A132739(a(n)) = A132740(n). - _Reinhard Zumkeller_, Aug 27 2007
%F a(n) = 2*A003602(n) - 1. - _Franklin T. Adams-Watters_, Jul 02 2009
%F a(n) = n/gcd(2^n,n). (This also shows that the true offset is 0 and a(0) = 0.) - _Peter Luschny_, Nov 14 2009
%F a(-n) = -a(n) for all n in Z. - _Michael Somos_, Sep 19 2011
%F From _Reinhard Zumkeller_, May 01 2012: (Start)
%F A182469(n, k) = A027750(a(n), k), k = 1..A001227(n).
%F a(n) = A182469(n, A001227(n)). (End)
%F a((2*n-1)*2^p) = 2*n - 1, p >= 0 and n >= 1. - _Johannes W. Meijer_, Feb 05 2013
%F G.f.: G(0)/(1 - 2*x^2 + x^4) - 1/(1 - x), where G(k) = 1 + 1/(1 - x^(2^k)*(1 - 2*x^(2^(k+1)) + x^(2^(k+2)))/(x^(2^k)*(1 - 2*x^(2^(k+1)) + x^(2^(k+2))) + (1 - 2*x^(2^(k+2)) + x^(2^(k+3)))/G(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, Aug 06 2013
%F a(n) = A003961(A064989(n)). - _Antti Karttunen_, Apr 15 2017
%F Completely multiplicative with a(2) = 1 and a(p) = p for prime p > 2, i.e., the sequence b(n) = a(n) * A008683(n) for n > 0 is the Dirichlet inverse of a(n). - _Werner Schulte_, Jul 08 2018
%F From _Peter Bala_, Feb 27 2019: (Start)
%F O.g.f.: F(x) - F(x^2) - F(x^4) - F(x^8) - ..., where F(x) = x/(1 - x)^2 is the generating function for the positive integers.
%F O.g.f. for reciprocals: Sum_{n >= 1} x^n/a(n) = L(x) + (1/2)*L(x^2) + (1/2)*L(x^4) + (1/2)*L(x^8) + ..., where L(x) = log(1/(1 - x)).
%F Sum_{n >= 1} x^n/a(n) = 1/2*log(G(x)), where G(x) = 1 + 2*x + 4*x^2 + 6*x^3 + 10*x^4 + ... is the o.g.f. of A000123. (End)
%F O.g.f.: Sum_{n >= 1} phi(2*n-1)*x^(2*n-1)/(1 - x^(2*n-1)), where phi(n) is the Euler totient function A000010. - _Peter Bala_, Mar 22 2019
%F a(n) = n - (1/2)*Sum_{d|2n} (-1)^d*phi(d). - _Ridouane Oudra_, May 01 2019
%F a(n) = A049606(n) / A049606(n-1). - _Flávio V. Fernandes_, Dec 08 2020
%F a(n) = numerator of n/2^(floor(n/2)). - _Federico Provvedi_, Dec 14 2021
%F a(n) = Sum_{d divides n} (-1)^(d+1)*phi(2*n/d). - _Peter Bala_, Jan 14 2024
%F a(n) = A030101(A030101(n)). - _Darío Clavijo_, Sep 19 2024
%e G.f. = x + x^2 + 3*x^3 + x^4 + 5*x^5 + 3*x^6 + 7*x^7 + x^8 + 9*x^9 + 5*x^10 + 11*x^11 + ...
%p A000265:=proc(n) local t1,d; t1:=1; for d from 1 by 2 to n do if n mod d = 0 then t1:=d; fi; od; t1; end: seq(A000265(n), n=1..77);
%p A000265 := n -> n/2^padic[ordp](n,2): seq(A000265(n), n=1..77); # _Peter Luschny_, Nov 26 2010
%t a[n_Integer /; n > 0] := n/2^IntegerExponent[n, 2]; Array[a, 77] (* Josh Locker *)
%t a[ n_] := If[ n == 0, 0, n / 2^IntegerExponent[ n, 2]]; (* _Michael Somos_, Dec 17 2014 *)
%o (PARI)
%o {a(n) = n >> valuation(n, 2)}; /* _Michael Somos_, Aug 09 2006, edited by _M. F. Hasler_, Dec 18 2014 */
%o (Haskell)
%o a000265 = until odd (`div` 2)
%o -- _Reinhard Zumkeller_, Jan 08 2013, Apr 08 2011, Oct 14 2010
%o (Scheme) (define (A000265 n) (let loop ((n n)) (if (odd? n) n (loop (/ n 2))))) ;; _Antti Karttunen_, Apr 15 2017
%o (Python)
%o from __future__ import division
%o def A000265(n):
%o while not n % 2:
%o n //= 2
%o return n # _Chai Wah Wu_, Mar 25 2018
%o (Java)
%o int A000265(n){
%o while(n%2==0) n>>=1;
%o return n;
%o }
%o /* _Aidan Simmons_, Feb 24 2019 */
%o (Julia)
%o using IntegerSequences
%o [OddPart(n) for n in 1:77] |> println # _Peter Luschny_, Sep 25 2021
%o (Magma)
%o A000265:= func< n | n/2^Valuation(n,2) >;
%o [A000265(n): n in [1..120]]; // _G. C. Greubel_, Jul 31 2024
%o (SageMath)
%o def A000265(n): return n//2^valuation(n,2)
%o [A000265(n) for n in (1..121)] # _G. C. Greubel_, Jul 31 2024
%Y Cf. A000004, A000010, A000123, A000217, A000225, A000265, A001227.
%Y Cf. A003602, A003961, A006516, A006519, A007814, A008683, A014577.
%Y Cf. A020988, A025480, A026741, A027750, A035263, A038502, A049606.
%Y Cf. A064989, A065330, A068563, A069834, A075101, A111929, A111930.
%Y Cf. A111918, A111919, A111920, A111921, A111922, A111923, A125650.
%Y Cf. A127793, A132739, A132740, A156769, A160469, A182469, A209308.
%Y Cf. A213671, A220466, A236999, A242603.
%Y Cf. A049606 (partial products), A135013 (partial sums), A099545 (mod 4), A326937 (Dirichlet inverse).
%Y Cf. A026741 (map), A001511 (converging steps), A038550 (prime index).
%Y Cf. A195056 (Dgf at s=3).
%K mult,nonn,easy,nice
%O 1,3
%A _N. J. A. Sloane_
%E Additional comments from _Henry Bottomley_, Mar 02 2000
%E More terms from Larry Reeves (larryr(AT)acm.org), Mar 14 2000
%E Name clarified by _David A. Corneth_, Apr 15 2017