Leading Digits in Fractional Parts of Square Roots
This is an archived, read-only copy of the United-TI subforum , including posts and topic from May 2003 to April 2012. If you would like to discuss any of the topics in this forum, you can visit Cemetech's Technology & Calculator Open Topic subforum. Some of these topics may also be directly-linked to active Cemetech topics. If you are a Cemetech member with a linked United-TI account, you can link United-TI topics here with your current Cemetech topics.

This forum is locked: you cannot post, reply to, or edit topics. Math and Science => Technology & Calculator Open Topic
Leading Digits in Fractional Parts of Square Roots
United-TI Archives -> Math and Science
 
    »
» View previous topic :: View next topic  
Author Message
Weregoose
Authentic INTJ


Super Elite (Last Title)


Joined: 25 Nov 2004
Posts: 3976
Posted: 23 Jun 2010 09:24:59 am    Post subject:
Carrying over from this thread, I decided to refine the search by gauging which of ten dissections of the natural numbers holds all of the square roots matching the initial digit of any given fraction. When the numbers are adjacent to each other within a group (for instance, [font=times new roman][size="3"]√61[/size] and [font=times new roman][size="3"]√62[/size] both "begin" with [font=times new roman][size="3"].8[/size]), only the foremost is considered. Fortunately, every case adopts the same linear recurrence, but with a different series of initial values.

The differences between these sequences and the central polygonal numbers [font=times new roman][size="3"](n–1)n+1[/size] (the "[font=times new roman][size="3"].5[/size]" set) can be described quite easily: I'll leave it up to you to extract it from the following code, if you think you're clever enough.

With D an integer representing the desired digit, seq(I[font=verdana]²-I+1-iPart(I-.2DI+.15D(D<6)),I,0,6 initiates the equation...

[font=times new roman][size="3"]an = an–7 – 2an–6 + an–5 – an–2 + 2an–1[/size]

...which is progressed by ΔList(cumSum(augment(Ans,{Ans(1)-2Ans(2)+Ans(3)-Ans(6)+2Ans(7.

Candidates (those outside of parentheses) are generated thus:

[font=courier new]D | [font=times new roman][size="3"]an[/size]
[font=courier new]0 | 1,0,1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289,324,...
[font=courier new]1 | (1,1,2,5,)10,17,27,38,51,66,83,103,124,147,172,199,229,260,293,328,...
[font=courier new]2 | (1,1,2,)5,(11,)18,28,39,52,68,85,105,126,149,175,202,232,263,296,332,...
[font=courier new]3 | (1,1,2,6,)11,19,29,40,54,69,87,107,128,152,177,205,235,266,300,335,...
[font=courier new]4 | (1,1,)2,6,12,20,30,41,55,71,89,109,130,154,180,208,238,269,303,339,...
[font=courier new]5 | (1,1,3,7,13,)21,31,43,57,73,91,111,133,157,183,211,241,273,307,343,...
[font=courier new]6 | (1,1,3,)7,13,22,32,44,58,74,93,113,135,159,185,214,244,276,310,346,...
[font=courier new]7 | (1,1,)3,(8,)14,23,33,45,60,76,95,115,137,162,188,217,247,279,314,350,...
[font=courier new]8 | (1,1,4,)8,15,24,34,47,61,78,97,117,140,164,191,220,250,283,317,354,...
[font=courier new]9 | (1,1,4,9,16,25,)35,48,63,80,99,119,142,167,194,223,253,286,321,358,...

And it goes without saying that for each "hit," reiterate with one higher until D is no longer matched.

Not necessarily for my purposes is the observation that they all converge on similar curves:

[font=courier new]D | [font=times new roman][size="3"]~an[/size]
[font=courier new]0 | [font=times new roman][size="3"](5x2 – 20x + 20)/5[/size]
[font=courier new]1 | [font=times new roman][size="3"](5x2 – 19x + 21)/5[/size]
[font=courier new]2 | [font=times new roman][size="3"](5x2 – 18x + 19)/5[/size]
[font=courier new]3 | [font=times new roman][size="3"](5x2 – 17x + 17)/5[/size]
[font=courier new]4 | [font=times new roman][size="3"](5x2 – 16x + 15)/5[/size]
[font=courier new]5 | [font=times new roman][size="3"](5x2 – 15x + 15)/5[/size]
[font=courier new]6 | [font=times new roman][size="3"](5x2 – 14x + 12)/5[/size]
[font=courier new]7 | [font=times new roman][size="3"](5x2 – 13x + 11)/5[/size]
[font=courier new]8 | [font=times new roman][size="3"](5x2 – 12x + 10)/5[/size]
[font=courier new]9 | [font=times new roman][size="3"](5x2 – 11x + 9)/5[/size]

I'll lastly note that their expansions bear a slight resemblance to the aforesaid differences.

*looks at clock* Yup, that's another all-nighter. Heaven.

Last edited by Guest on 24 Jun 2010 12:55:27 am; edited 1 time in total
Back to top
Weregoose
Authentic INTJ


Super Elite (Last Title)


Joined: 25 Nov 2004
Posts: 3976
Posted: 09 Aug 2010 07:52:31 pm    Post subject:
(Insert goes-without-saying disclaimer on rounding issues.)

Fairly well-known is the fact that the continued fraction of a square root holds twice its integer part. With 14 digits of precision, this in't very useful if large periods are involved. This is all pretty much an "inb4" – I found something that doesn't even use continued fractions.

For [font=times new roman][size="3"]b[/size] equal to the fractional part of [font=times new roman][size="3"]√a[/size], there is a number [font=times new roman][size="3"]c[/size] for which [font=times new roman][size="3"]c/b[/size] minus [font=times new roman][size="3"]b[/size] is an integer, and that happens to be the distance from [font=times new roman][size="3"]a[/size] to the first perfect square lower than [font=times new roman][size="3"]a[/size]. Alternatively, [font=times new roman][size="3"]c/(1–b)[/size] minus [font=times new roman][size="3"]b[/size] is an integer if [font=times new roman][size="3"]a[/size] plus [font=times new roman][size="3"]c[/size] is the next perfect square higher than [font=times new roman][size="3"]a[/size].

What this gives rise to is an algorithm where the number of steps needed to find the unknown is essentially how far away it is from a perfect square. To decide which way would be faster, simply ask whether [font=times new roman][size="3"]b[/size] is higher or lower than [font=times new roman][size="3"]1/2[/size]. All that follows is to use an expression to convert the [font=times new roman][size="3"]c[/size] that we found (and the [font=times new roman][size="3"]b[/size] that we started with) back into [font=times new roman][size="3"]a[/size]. Thus:

fPart(√(A→B
For(C,1,E9)
If fPart(round(C/Ans-Ans
End
(C+Ans[font=verdana]²)[font=verdana]²/(4Ans[font=verdana]²)

+

1-fPart(√(A→B
For(C,1,E9)
If fPart(round(C/Ans+Ans
End
(C+Ans[font=verdana]²)[font=verdana]²/(4Ans[font=verdana]²)-C

=

fPart(√(A→B
Ans>.5→D
fPart(Ans-B
For(C,1,E9)
If fPart(round(C/Ans-Ans+2DAns
End
(C+Ans[font=verdana]²)[font=verdana]²/(4Ans[font=verdana]²)-CD

Clearly, the worst-case scenario is using the input closest to the average of two neighboring squares. Choosing 1,523,991, I'll compare times between the above and the [font=times new roman][size="3"]O[/size]([font=times new roman][size="3"]n½[/size]) algorithm seen here:

fPart(√(A))[font=verdana]²
While fPart(round(Ans
Ans+1+2√(Ans
End
Ans

This one took 1234 iterations and approximately 17 seconds to find [font=times new roman][size="3"]a[/size]. The one detailed earlier in this post also took 1234 steps (meaning that its worst-case number of iterations ties with the other algorithm's normal count), and got the same result in about 20 seconds—however, as its inputs draw close to a perfect square, the answer would be produced immediately (with the time spent on each input decrementing linearly until that point), whereas the other algorithm would still take about [font=times new roman][size="3"]√a[/size] steps to finish.

Yet, as a final consequence of the fact that the worst-case scenario entails an equal number of steps shared between both algorithms, the ending times will be just a factor of a single iteration of each, meaning that the simpler algorithm will always win out as the faster one should the input's distances between adjacent squares balance out.

Last edited by Guest on 09 Aug 2010 08:45:27 pm; edited 1 time in total
Back to top
Weregoose
Authentic INTJ


Super Elite (Last Title)


Joined: 25 Nov 2004
Posts: 3976
Posted: 11 Aug 2010 10:47:22 am    Post subject:
With extraordinary luck, I was able to pry the following from the hands of a pattern I noticed:

fPart(√(A→B
1/fPart(Ans‾¹→D
For(C,0,E9
round(BD+CD,3
If fPart(Ans
End
(Ans+B[font=verdana]²)[font=verdana]²/(4B[font=verdana]²

There have to be better algorithms still; I won't stop trying until I've found them!

What I've found very quickly using this:

[font=times new roman][size="3"]217822 ≈ (√(200)/3 + 462)2

41041 ≈ (204 – √(2))2

φ = √(5/4) + 1/2

38 ≈ √(1961) – 2π
[/size]

Last edited by Guest on 11 Aug 2010 11:24:00 am; edited 1 time in total
Back to top
Weregoose
Authentic INTJ


Super Elite (Last Title)


Joined: 25 Nov 2004
Posts: 3976
Posted: 30 Aug 2010 12:08:54 pm    Post subject:
Extracting X from fPart(√(X)) and 1/fPart(√(X)):

fPart(√(X→A
Ans‾¹→B
A
While fPart(round(Ans,4
Ans-B
End
(A-.5Ans)[font=verdana]²

Extracting X from fPart(√(X)) and 1/fPart(1/fPart(√(X))), which seems to be generally faster:

fPart(√(X→A
1/fPart(Ans‾¹→B
AAns
While fPart(round(Ans,4
B+Ans
End
(A+Ans/A)[font=verdana]²/4


Last edited by Guest on 30 Aug 2010 12:43:11 pm; edited 1 time in total
Back to top
Xeda112358


Active Member


Joined: 19 May 2009
Posts: 520
Posted: 27 Jan 2011 10:26:04 am    Post subject:
I am completely confused about what you are doing Razz (and yes, I know this is a necro-ish post, but I like numbers). I like to play with numbers, but I don't really speak math.

Again, sorry for necro posting, but I am curious...
Back to top
Display posts from previous:   
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
Leading Digits in Fractional Parts of Square Roots
    »
» View previous topic :: View next topic  
Page 1 of 1 » All times are UTC - 5 Hours

 

Advertisement