Hacker News Reader

Comment by tlonny | Hacker News Reader

My understanding (which might be wrong) is that just because PI is infinite and non-repeating, doesn't necessarily mean that every conceivable pattern of digits is present.

As a contrived example, consider the pattern:

01 001 0001 00001 etc.

This pattern is infinite and never repeats but we will never see two consecutive "1"s next to each other.

View on HN

Yes, it doesn't necessarily follow, but it is indeed conjectured that pi is a normal number, meaning all digits appear with the same frequency, but it is not known yet. https://en.wikipedia.org/wiki/Normal_number

The same frequency does not imply every subsequence appears. Consider the modification which rewrites every sequence of 123 to 132. All digits will have the same frequency but 123 will never appear.

If pi is shown to be normal in every base then every finite sequence must appear in it.

You haven't read the link you posted though. Every digit appearing with the same frequency means a number is simply normal and it is not enough to get you what you want in this case (as pointed out by sibling comment). Normal number is a number where every possible string of length n has the same frequency of 10^(-n)

No, you haven't read the link he posted. https://en.wikipedia.org/wiki/Normal_number#Definitions: "A disjunctive sequence is a sequence in which every finite string appears. A normal sequence is disjunctive". If Pi is normal, then it is also disjunctive.

When I was at university, one of the senior number theory professors allegedly said during a tutorial that he accepts the normality of pi on the basis of "proof by why the hell wouldn't it be". With tongue in cheek, of course.

The difference might be:

For your example there is an algorithm to describe the sequence of digits and for Pi there isn't.

EDIT + Clarification: There is an algorithm to calculate the digits of your number without calculating all previous digits. But for pi there isn't.

There is one, how do you think we compute digits of pi.

So here's a bet:

I give you the 10^100th digit of the above algorithm and you give me the 10^100th digit of pi.

Whoever fails owes the other side 10 BTC.

There is an algorithm to get the nth digit of pi. It's just that it does not run in constant time

I kind of addressed this here: https://news.ycombinator.com/item?id=31966228

If your argument is "These algorithms have differing degrees of computational complexity" then that doesn't actually demonstrate that one can't be algorithmically determined

What I meant is:

Describe the n-th digit of an irrational number without calculating all previous positions of the number.

If pi were a sequence of digits, there is no algorithm to calculate it other than by calculating pi but there is one for op's number. The very fact that he could show the algorithm for creating the sequence of numbers in his post is indicative of that.

For pi such an algorithm doesn't exist (other than calculating pi itself).

I wanted to emphasize this by talking about the "sequence of digits" in my original reply but apparently I failed at explaining this well.

Various algorithms to compute the n-th digit of pi exist, eg https://bellard.org/pi/pi_n2/pi_n2.html.

I can't really tell to what extent you're not computing previous digits (or doing work that could quickly be used to come up with these previous digits) with this algorithm but O(n^2) seems quite heavy compared to O(1) (I expect) to get the n'th digit of op's number.

Maybe I should rephrase it:

My assumption is: If there is an O(1) algorithm to determine the n-th digit of an irrational number x then the number is still "of a different class" than the likes of pi and there OP might not be able to induce things from this "lesser class of irrational numbers"

However, it's just an intuition

How could it possibly be O(1)? That doesn't even give you time to read every bit of the input number.

Why, how is that related to the existence of an algorithm?

I narrowed down "algorithm" to a specific sort of algorithm in the original reply.

Ok! I'll let you know when I'm finished calculating - hope you're still alive by then

>There is an algorithm to calculate the digits of your number without calculating all previous digits. But for pi there isn't.

Actually, there is: https://math.hmc.edu/funfacts/finding-the-n-th-digit-of-pi/

Reply on news.ycombinator.com