High-Water Mark

Author

Eric W. Weisstein
November 1, 2005

This notebook downloaded from http://mathworld.wolfram.com/notebooks/IntegerSequences/High-WaterMark.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/High-WaterMark.html.

©2005 Wolfram Research, Inc. except for portions noted otherwise

Inialization

Example

l=Table[Random[Integer,{1,10}],{10}]

l={3,5,7,8,8,5,7,9,2,5};

RunningMaxima[l]

HighWaterMarks[l]

Expected Number of Maxima

l=Table[Random[],{10000},{100}];//Timing

This could be done much more efficiently...

With[{n=50},
{Mean[Length/@First/@HighWaterMarks/@(Take[#,n]&/@l)],HarmonicNumber[n]}
]//N//Timing

{Mean[Length/@First/@HighWaterMarks/@l],HarmonicNumber[100]}//N//Timing

data=Table[Mean[Length/@First/@HighWaterMarks/@(Take[#,n]&/@l)],{n,100}];//Timing

<<Utilities`Plot`

ListPlot[HarmonicNumber[Range[100]],Prolog->{PointSize[.01],Blue,Point/@MapIndexed[{#2[[1]],#1}&,data]},PlotJoined->True,PlotStyle->Red,
AxesLabel->TraditionalForm/@{n,{StyleForm[Subscript[OverBar[x],n],FontColor->Red],StyleForm[Subscript[H,n],FontColor->Blue]}}
]

Floor[HarmonicNumber[Range[50]]]

Flatten[n/.Table[FindRoot[HarmonicNumber[n]==k,{n,1,100}],{k,10}]]//Ceiling

l=Flatten[n/.Table[FindRoot[HarmonicNumber[n]==10^k,{n,1,10^10},MaxIterations->1000,WorkingPrecision->1000],{k,0,3}]]//Ceiling//Timing

Ceiling[n/.FindRoot[HarmonicNumber[n]==10^3,{n,1,10^10},MaxIterations->2000,WorkingPrecision->1500]]//Timing