Have you ever seen such a math problem?
"On this paper, The number 1 is ■, the number 2 is ■, The number 3 is ■ pieces, numbers other than 1 to 3 The number is written in ■. "
A piece of mysterious paper has fallen. On this paper, the paper itself is written. However, the four numbers written in ■ have disappeared and I can't read them. Please put a number in ■ to make this sentence correct.
The answers are 4, 1, 3, 1 in order. Please actually apply the numbers and check This is a high school math level combination problem.
Strange things happen when you self-refer to yourself in this way.
Can there be a program that determines if it loops infinitely within the program?
It may lead to the problem. No such program can exist. But what about the next problem?
"This sentence contains () the number 1"
Let's apply 1 to (). Then
"This sentence contains (1) the number 1."
It will be. Since 1 appears twice in total in the sentence, it contradicts the meaning of the sentence. The number in () is not 1.
Let's apply an integer other than 1 that is 9 or less.
Then, 1 appears only once in the text, but () should have been other than 1, so it is a contradiction. In other words, it is not an integer other than 1 that is 9 or less.
So is it 10 or more? No way. It wouldn't be possible.
In other words, there is no integer in ().
I was able to prove that it is mathematically impossible. Yes, the end
Does the answer really exist? No exist. It's infinite.
Click here for the model answer
\frac{1}{2}+\frac{3}{2}
The above formula contains only one 1. Therefore, a total of 1 appears twice in the text. Also, if you calculate the above formula, the result will be 2.
In this way, the result of the operation between real numbers should match the number of 1s that appear in the formula.
Below is the example.
\lceil \sqrt{2} \rceil ,(6-5)
,\cos^2 49^ \circ +\sin^2 49^\circ, etc \cdots
Certainly, it feels like. But i don't really like it I think it's just an expression, not a number.
"There are $ 1/2 + 3/2 $ apples" in everyday life I don't say that. A calculator is enough to treat an expression as a number.
Then I came up with the binary notation of integers. For example, apply 0010b to () in the text. A total of 1 appears twice in the text. Also, since 0010b represents 2 in decimal notation, I was able to compose sentences without contradiction.
In binary notation, only 0s and 1s represent numbers, so this method can enumerate numbers that are semantically consistent.
And if you put the integer sequence in the online integer dictionary, it might become popular ...
I immediately wrote the program. It's a simple program that takes about 3 minutes.
As an aside, I would like to introduce the internal implementation of Java's Integer.bitCount because it is interesting.
public static int bitCount(int i) { i = i - ((i >>> 1) & 0x55555555); i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); i = (i + (i >>> 4)) & 0x0f0f0f0f; i = i + (i >>> 8); i = i + (i >>> 16); return i & 0x3f; }
With this alone, we can count the number of 1 bits of int. Just shifts and logical operations without using control syntax such as loops and conditionals I can implement it ... The amount of calculation is $ O (1) $ because no loop is used. Wow This is based on a string search algorithm called the wavelet tree.
Now, let's get back to the main subject. Run the program. With excitement ./test.out 2000 What a hit. Then the execution result is
2 3
that? only this? Increasing the number does not change the result. It seems to work properly inside.
That's right. If you think about it, the rate of increase in the number of 1-bit integers is at least Since it can be kept below $ \ log_2 n $, it cannot compete with $ n $, which increases linearly.
I'm embarrassed that I didn't realize such a natural thing
The proof below
For an integer $ n $ greater than or equal to 0
Define the function $ B (n) $ as follows
$ B (n) $: = {number of 1 bits when $ n $ is expressed in binary notation}
That is,
By definition $ B (n) $ is
The equation holds for $ n = 4 $
From this, $ 0 \ le n \ le 4 $ was shown.
Therefore, only a few integers satisfy the equation.
It was kind of natural.
It was a problem that I thought was so interesting that I couldn't sleep at night, but in reality A natural result with no surprises.
What is it dented?
Lesson: Most ideas that come up before going to bed have pitfalls.
that's all.