A065937 a(n) is the integer (reduced squarefree) under the square root obtained when the inverse of Minkowski's question mark function is applied to the n-th ratio A007305(n+1)/A047679(n-1) in the full Stern-Brocot tree and zero when it results a rational value.

0, 0, 0, 5, 5, 0, 0, 0, 2, 2, 0, 5, 5, 0, 0, 2, 3, 0, 3, 3, 0, 3, 2, 0, 2, 2, 0, 5, 5, 0, 0, 5, 13, 17, 2, 17, 37, 5, 13, 13, 5, 37, 17, 2, 17, 13, 5, 2, 3, 0, 3, 3, 0, 3, 2, 0, 2, 2, 0, 5, 5, 0, 0, 3, 17, 3, 37, 21, 13, 10, 37, 3, 401, 6, 13, 10, 401, 0, 17, 17, 0, 401, 10, 13, 6, 401, 3, 37

Offset: 1

Author

Antti Karttunen, Dec 07 2001

Keywords

• nonn

Comments

Note: the underlying function N2Q (see the Maple code) maps natural numbers 1, 2, 3, 4, 5, ..., through all the positive rationals 1/1, 1/2, 2/1, 1/3, 2/3, 3/2, 3/1, 1/4, ... bijectively to the union of positive rationals and quadratic surds.

In his "On Numbers and Games", Conway denotes Minkowski's question mark function with x enclosed in a box.

Examples

			The first few values for this mapping are
  N2Q(1)  = Inverse_of_MinkowskisQMark(1)   = 1,
  N2Q(2)  = Inverse_of_MinkowskisQMark(1/2) = 1/2,
  N2Q(3)  = Inverse_of_MinkowskisQMark(2)   = 2,
  N2Q(4)  = Inverse_of_MinkowskisQMark(1/3) = (3-sqrt(5))/2,
  N2Q(5)  = Inverse_of_MinkowskisQMark(2/3) = (sqrt(5)-1)/2,
  N2Q(6)  = Inverse_of_MinkowskisQMark(3/2) = 3/2,
  N2Q(7)  = Inverse_of_MinkowskisQMark(3)   = 3,
  N2Q(8)  = Inverse_of_MinkowskisQMark(1/4) = 1/3,
  N2Q(9)  = Inverse_of_MinkowskisQMark(2/5) = sqrt(2)-1,
  N2Q(10) = Inverse_of_MinkowskisQMark(3/5) = 2-sqrt(2).
		

References

• J. H. Conway, On Numbers and Games, 2nd ed. Natick, MA: A. K. Peters, pp. 82-86 (First ed.), 2000.

Links

• Robert Hill, An article in sci.math newsgroup
• Eric Weisstein's World of Mathematics, Minkowski's Question Mark Function.
• Wikipedia, Minkowski's question mark function
• Index entries for sequences related to Minkowski's question mark function
• Index entries for sequences related to Stern's sequences

Crossrefs

a(n) = A065936(A065935(n)). Positions of sqrt(n) in this mapping: A065939.

Programs

Maple

[seq(find_sqrt(N2Q(j)),j=1..512)];
N2Q := n -> Inverse_of_MinkowskisQMark(A007305(m+1)/A047679(m-1));
Inverse_of_MinkowskisQMark := proc(r) local x,y,b,d,k,s,i,q; x := numer(r); y := denom(r); if(1 = y) then RETURN(x/y); fi; if(2 = y) then RETURN(x/y); fi; b := []; d := []; k := 0; s := 0; i := 0; while(x <> 0) do q := floor(x/y); if(i > 0) then b := [op(b),q]; d := [op(d),x]; fi; x := 2*(x-(q*y)); if(member(x,d,'k') and (k > 1) and (b[k] <> b[k-1]) and (q <> floor(x/y))) then s := eval_periodic_confrac_tail(list2runcounts(b[k..nops(b)])); b := b[1..(k-1)]; break; fi; i := i+1; od; if(0 = k) then b := b[1..(nops(b)-1)]; b := [op(b),b[nops(b)]]; fi; RETURN(factor(eval_confrac([floor(r),op(list2runcounts([0,op(b)]))],s))); end;
eval_confrac := proc(c,z) local x,i; x := z; for i in reverse(c) do x := (`if`((0=x),x,(1/x)))+i; od; RETURN(x); end;
eval_periodic_confrac_tail := proc(c) local x,i,u,r; x := (eval_confrac(c,u) - u) = 0; r := [solve(x,u)]; RETURN(max(r[1],r[2])); end; # Note: I am not sure if the larger root is always the correct one for the inverse of Minkowski's question mark function. However, whichever root we take, it does not change this sequence, as the integer under the square root is same in both cases. - Antti Karttunen, Aug 26 2006
list2runcounts := proc(b) local a,p,y,c; if(0 = nops(b)) then RETURN([]); fi; a := []; c := 0; p := b[1]; for y in b do if(y <> p) then a := [op(a),c]; c := 0; p := y; fi; c := c+1; od; RETURN([op(a),c]); end;
find_sqrt := proc(x) local n,i,y; n := nops(x); if(n < 2) then RETURN(0); fi; if((2 = n) and (`^` = op(0,x)) and (1/2 = op(2,x))) then RETURN(op(1,x)); else for i from 0 to n do y := find_sqrt(op(i,x)); if(y <> 0) then RETURN(y); fi; od; RETURN(0); fi; end; # This returns an integer under the square-root expression in Maple.

Extensions

Description clarified by Antti Karttunen, Aug 26 2006