The On-Line Encyclopedia of Integer Sequences (OEIS)

Revision History for A007305 (Bold, blue-underlined text is an addition; faded, red-underlined text is a ~~deletion~~.)
Showing entries 1-10 | older changes

A007305

Numerators of Farey (or Stern-Brocot) tree fractions.
(history; published version)

#111 by Joerg Arndt at Sat Aug 03 01:49:05 EDT 2024

STATUS

reviewed

approved

#110 by Michel Marcus at Sat Aug 03 01:26:33 EDT 2024

STATUS

proposed

reviewed

#109 by Jason Yuen at Fri Aug 02 23:43:05 EDT 2024

STATUS

editing

proposed

#108 by Jason Yuen at Fri Aug 02 23:43:00 EDT 2024

FORMULA

a((2^(m+2)-k) = A007306(2^(m+1)-k), m=0,1,2,..., k=0,1,2,...,2^m-1. - Yosu Yurramendi, Jul 04 2014

STATUS

approved

editing

#107 by N. J. A. Sloane at Wed Apr 24 12:39:19 EDT 2024

STATUS

proposed

approved

#106 by Peter Luschny at Wed Apr 24 06:39:59 EDT 2024

STATUS

editing

proposed

Discussion

Wed Apr 24

08:16

Kevin Ryde: It's a lot easier than that.  The mathematica product of L or R matrices according as the bits of n is one way.  Or in a procedural language just do the matrix actions as x+=y or y+=x.  The only subtlety is getting the bits and the x/y the right way around.  Eg. in pari,

A007305(n) = {
  if(n<=1, n,
     n--; my(x=1,y=1);
     for(i=0,logint(n,2)-1,
         if(bittest(n,i), x+=y, y+=x));
     x);
}

08:37

Peter Luschny: Kevin, I had hoped to see you here. Surely you will contribute your formula? Could you please also take a look at A372205?

09:36

Kevin Ryde: About A372205, I can't divine anything.  Mikhail knew something, possibly some combinatoric counting done in bits, but can't tell what.

09:55

Kevin Ryde: About here, I'll have a little dig for whether there's a choice reference.

#105 by Peter Luschny at Wed Apr 24 06:05:12 EDT 2024

MAPLE

SternBrocotTreeNum := proc(n) option remember; local msb, r; if(n < 2) then RETURN(n); fi; msb := floor_log_2(n); r := n - (2^msb); if(floor_log_2(r) = (msb-1)) then RETURN(SternBrocotTreeNum(r) + SternBrocotTreeNum(((3*(2^(msb-1)))-r)-1)); else RETURN(SternBrocotTreeNum((2^(msb-1))+r)); fi; end; # Antti Karttunen, Mar 19 2000 [Broken program - N. J. A. Sloane, Aug 05 2020]

if ilog2(r) = msb - 1 then b(r) + b(3*2^(msb-1) - r - 1) else b(2^(msb - 1) + r) fi end: if n = 0 then 0 else b(n-1) fi end: # _Antti Karttunen_, Mar 19 2000 [Corrected and rewritten by _Peter Luschny_, Apr 24 2024]

# Antti Karttunen, Mar 19 2000 [Corrected and rewritten by Peter Luschny, Apr 24 2024]

Discussion

Wed Apr 24

06:38

Peter Luschny: Note that the deleted program had the notice: [Broken program - N. J. A. Sloane, Aug 05 2020]

#104 by Peter Luschny at Wed Apr 24 06:04:27 EDT 2024

MAPLE

A007305 := proc(n) local b; b := proc(n) option remember; local msb, r;

if n < 3 then return 1 fi; msb := ilog2(n); r := n - 2^msb;

if ilog2(r) = msb - 1 then b(r) + b(3*2^(msb-1) - r - 1) else b(2^(msb - 1) + r) fi end: if n = 0 then 0 else b(n-1) fi end:

# Antti Karttunen, Mar 19 2000 [Corrected and rewritten by Peter Luschny, Apr 24 2024]

seq(A007305(n), n = 0..92);

#103 by Peter Luschny at Wed Apr 24 05:00:53 EDT 2024

COMMENTS

From Reinhard Zumkeller, Dec 22 2008: (Start)

For n>1: a(n+2) = if A025480(n-1) != 0 and A025480(n) != 0 then a(A025480(n-1)+2) + a(A025480(n)+2) else if A025480(n)=0 then a(A025480(n-1)+2)+1 else 0+a(A025480(n-1)+2);

a(A054429(n)+2) = A047679(n) and a(n+2) = A047679(A054429(n));

A153036(n+1) = floor(a(n+2)/A047679(n)). (End)

FORMULA

From Reinhard Zumkeller, Dec 22 2008: (Start)

For n > 1: a(n+2) = if A025480(n-1) != 0 and A025480(n) != 0 then a(A025480(n-1)+2) + a(A025480(n)+2) else if A025480(n)=0 then a(A025480(n-1)+2)+1 else 0 + a(A025480(n-1)+2).

a(A054429(n)+2) = A047679(n).

a(n+2) = A047679(A054429(n)).

A153036(n+1) = floor(a(n+2)/A047679(n)). (End)

STATUS

approved

editing

Discussion

Wed Apr 24

05:02

Peter Luschny: Formulas moved to the correct section.

05:18

Peter Luschny: Maybe someone can get Zumkeller's recipe to work?

#102 by Michael De Vlieger at Tue Apr 18 09:44:32 EDT 2023

STATUS

proposed

approved