More of a puzzle than a math question..
As you all know, there are seven tetrominos, the five shown here and the mirrored versions of the two asymmetric ones:
I was wondering: What's the smallest rectangle you can completely fill with tetrominoes so that no two equal tetrominoes touch each other?
(Let's skip the two trivial solutions and require two or more tetrominoes)
Wikipedia shows a solution to a different tiling problem, but by removing the rightmost 4x1 tile it yields a solution to mine with 4x9:
Unfortunately, I couldn't find anything smaller. The corners are tricky. Are you more lucky? Otherwise I'll probably try to write a small program over the weekend.
And I'm aware there's a lot of stuff on tetromino tiling on the net, but I couldn't find anything matching my specific problem.
Joined: 5/2/2006
Posts: 1020
Location: Boulder, CO
Requiring at least 2 tetrominos, The answer is 3, using the colors of the tetrominoes you show, it would be a 3X4 rectangle filled with an orange "L" a green "s" and another orange "L".
#0##
#00#
##0#
You can prove that this is at least tied for the optimal solution, because any solution with fewer tetrominos (again, ignoring the examples of 1 tetronimo) would have to have 2 exactly, making the total area 8.
That means that the rectangle it would have to fill would be either 2 by 4 or 1 by 8. the 1 by 8 could only include 1x4 tetronimos, so the two would touch. The 2 by 4 case you either be 2 long thin ones, 2 squares, or 2 orange "L"s. In all of these cases, two like tetronimos would touch.
Are your requiring that all tetronimos appear in the solution? in that case this answer is no good.
it would be a 3X4 rectangle filled with an orange "L" a green "s" and another orange "L".
Of course. That satisfied the requirements as stated, though for my unstated purpose of "looks like tetris when painted on stuff", it won't really do. ;) Thanks!
Twelvepack wrote:
You can prove that this is at least tied for the optimal solution
There's tie at 2x6
#----%
###%%%
which I also didn't consider due to the reasons mentioned above.
Twelvepack wrote:
Are your requiring that all tetronimos appear in the solution? in that case this answer is no good.
Oh how I'd like to have a rectangle with each tetronimo exactly once! Unfortunately, that isn't possible. You need an even amount of T shapes. And "every tile once and T twice" is at least 8x4.
If you look at my avatar, you'll notice that from each vertex of each square, a line segment is drawn in its interior at a certain angle (0 to 45 degrees) clockwise from one of the sides; the points of intersection of pairs of these line segments are the vertices of the next square in the series.
As this angle (t) varies, how do the positions of the vertices of the interior squares vary? I first thought this through for the first square with Cartesian coordinates, setting the outermost square to have one vertex at the origin and the opposite vertex at (1,1), and it was elementary, but I suspect it would be easier to use polar coordinates and center the outermost square at the origin.
The older version of my avatar is below, for reference:
Here is the diagram I created below (reflected from the avatar image):
The intersection of the "square chords" are at 90° angles. As t increases, the intersection marked with the right angle sign traces the arc of a circle where the bottom edge of the square is a diameter for the circle. (If there are three points A,B,C on a circle and angle ACB is 90°, then AB forms a diameter for the circle.)
Thus, assuming the square's vertices are at (0,0), (0,1), (1,0) and (1,1), the marked intersection is at (0.5 + 0.5 cos(2t) , 0.5 sin(2t)). Or, in polar coordinates, (cos(t),t), where t functions as θ and r=cos(θ).
Edit: The distance from the bottom-left corner to the marked intersection is cos(t) and the distance from the bottom-right corner to the same is sin(t). That means the inner square has side length |cos(t)-sin(t)| and its area is (cos(t)-sin(t))²=1-sin(2t).
That's how it goes for the first one, and the way the positions of the innermost vertices varies with t is even more amazing, like if you start with the square centered at the origin in polar coordinates, and one corner of the outermost square is at angle 0, then one of the corners (let's call it the "first corner") of the next square inward is rotated by t and dilated by sqrt(1-sin(2t)), so something like the graph of r=sqrt(1-sin(2t/3))^3 (position of the first corner of the third square inward) is a somewhat tightly-wound spiral, and examination of a restricted domain (like t in [pi/12,pi/6]) shows that the tendency is for the inner squares to get very small very quickly as n increases in r=sqrt(1-sin(2t/n))^n.
I reached the limits of my mathematical knowledge when a question came up whether you can represent all real numbers using decimal notation.
On one hand, the set of reals is uncountable while the set of integers is countable, and therefore it would seem to me that you cannot represent all possible reals with integral digits.
On the other hand, are there real numbers that cannot be represented with integral digits, when we allow an infinite amount of digits? My intuition would say yes, because a countably infinite amount of digits (from a finite set of them) doesn't somehow turn uncountable. Or does it? If it doesn't, then there would be real numbers that cannot be expressed even with infinitely many digits, but if there are, what would they be?
Strangely, I don't know the answer to this, even though I really should.
I reached the limits of my mathematical knowledge when a question came up whether you can represent all real numbers using decimal notation.
On one hand, the set of reals is uncountable while the set of integers is countable, and therefore it would seem to me that you cannot represent all possible reals with integral digits.
On the other hand, are there real numbers that cannot be represented with integral digits, when we allow an infinite amount of digits? My intuition would say yes, because a countably infinite amount of digits (from a finite set of them) doesn't somehow turn uncountable. Or does it? If it doesn't, then there would be real numbers that cannot be expressed even with infinitely many digits, but if there are, what would they be?
Strangely, I don't know the answer to this, even though I really should.
Aren't (finite) decimal expansions essentially just successively better approximations to the number in question? I think your question is answered in that sense: all real numbers can be represented by an infinite number of digits because there is no countable way to cycle through them.
For example, if you tried to represent all numbers by way of
1) 0.1
2) 0.2
3) 0.3
...
9) 0.9
10) 0.10
11) 0.11
12) 0.12
...
then you would never reach the decimal expansion for the square root of 2. That is, there is no finite number that encodes the square root of 2's decimal expansion. This would seem to indicate that when we switch to a countably infinite number of digits, the set does indeed become uncountable (see Cantor's diagonal argument). I guess what I'm trying to say is that even though the decimal expansions themselves are countably infinite, the set of all such decimal expansions is uncountably infinite. For more information, research the power set.
(I later decided to bold this because I think it is the most succinct answer to your question.)
However, my guess is that there are hyperreal numbers that cannot be expressed through decimal expansion. I don't know for sure, since I don't have much expertise in them.
Infinite sets and cardinality are really unintuitive.
At first, it's extremely unintuitive that the set of rational numbers is exactly as big as the set of natural numbers, even though intuition would tell that of course there are enormously more rational numbers than natural ones. Intuition would be wrong.
After understanding the reasoning behind it (mainly, that you can unambiguously map each natural number to a rational number, which makes the sets equal in size), one gets to accept that yes, there are as many. Then the next unintuitive step is to understand why the set of real numbers is genuinely "larger" than the set of rational numbers. (This is quite unintuitive because between any two rational numbers there is an infinite amount of real numbers, and between any two real numbers there is an infinite amount of rational numbers. Intuition would conclude that the sets are therefore comparable in size. Yet somehow there are more real numbers than rational ones. This is quite unintuitive.)
Then, when one finally accepts (at least at some level) that there really are more real numbers than rational numbers (because it can be proven that it's not possible to construct a one-to-one mapping between them), comes the next unintuitive step: Even though the set of real numbers is genuinely larger than the set of natural numbers, you can still represent every single real number with decimal digits (which are, rather obviously, natural numbers.) Intuition fails once again. "But wait, you just said a second ago that there are more real numbers than natural numbers, which means that there is no one-to-one mapping between them. Now you are telling that you can represent every single real number with a string of natural numbers? Isn't that a contradiction?"
Thus the next unintuitive step that one has to understand is that even though the set of natural numbers is countable, the set of all possible combinations of decimal digits is uncountable, just like the set of reals (and therefore reals can be represented with decimal digits)... This means that there is no one-to-one mapping between the set of natural numbers and the set of all possible combinations of natural numbers... which is very counter-intuitive. One would think that you could number each combination uniquely.
Regarding a question I have asked previously in this thread, namely: "Is the set of all points inside a unit square as big as the set of all points on a unit line?"
If the two sets are equal in size, that means that there exists an unambiguous one-to-one mapping between all the points on the line and all the points in the square. Would this be a valid such mapping?
Take the decimal representation of the x and y coordinates of the point inside the square, and interleave each decimal digit to get a value between 0 and 1 (which would therefore correspond to a value on the unit line).
For example, if the point is (0.1234, 0.5678) then its mapping onto the unit line would be 0.15263748. Or for example (0.12, 0.3456) would map to 0.13240506.
Does that work? Or is it ambiguous (ie. more than one point in the square would map to the same point on the unit line)?
Regarding a question I have asked previously in this thread, namely: "Is the set of all points inside a unit square as big as the set of all points on a unit line?"
If the two sets are equal in size, that means that there exists an unambiguous one-to-one mapping between all the points on the line and all the points in the square. Would this be a valid such mapping?
Take the decimal representation of the x and y coordinates of the point inside the square, and interleave each decimal digit to get a value between 0 and 1 (which would therefore correspond to a value on the unit line).
For example, if the point is (0.1234, 0.5678) then its mapping onto the unit line would be 0.15263748. Or for example (0.12, 0.3456) would map to 0.13240506.
Does that work? Or is it ambiguous (ie. more than one point in the square would map to the same point on the unit line)?
I've heard of that method before, and yes it works. Both sets have the same cardinality of C. Give me a minute to look it up on Wikipedia...
(Nope, can't find it. However, I did find this article on space-filling curves.)
I'd be interested in whether mapping R to R2 causes any "difficulties". From what I can tell, you may sacrifice the notion of a metric since the curve must necessarily be of infinite length. Any mathematicians want to weigh in?
As for your previous post, you are correct that the distinction between the rationals or reals and the irrationals is very sticky to pin down. I think your assertion needs refinement, though: every real number can be represented to arbitrary precision by a finite string of natural numbers. Once you want to represent a number by its "true" decimal expansion, the number of digits necessary blows up too much and you end up unable to represent all the reals. Note that these so-called "true" representations (infinite decimal expansions) are essential to Cantor's diagonal argument-- you need the infinitude of digits to construct a new number that is still real but not on the list of real numbers.
This reminds me of a conversation I had with a friend in high school. I had learned enough at that point to know that the digits of pi are "random" (which I now know hasn't actually been proven...) but my friend said that it has to settle down at some point into some kind of repeating decimal or pattern. I said no, it doesn't, but he just couldn't wrap his head around the idea that pi was transcendental.
As a physicist, I actually don't care much about real vs. rational numbers or greater-than vs. greater-than-or-equal-to signs, but if you put up with the convoluted real analysis long enough, you just learn to accept it as already proven.
I think your assertion needs refinement, though: every real number can be represented to arbitrary precision by a finite string of natural numbers. Once you want to represent a number by its "true" decimal expansion, the number of digits necessary blows up too much and you end up unable to represent all the reals.
But I'm not talking about finite representations. What I'm saying is that, if I understand correctly, any real number can be represented completely accurately by an infinite string of digits. Not just as an arbitrarily close approximation, but the exact accurate value.
A consequence of this is that, unintuitively, the set of all possible infinite strings of digits is uncountable (and at least as large as the set of reals.)
This reminds me of a conversation I had with a friend in high school. I had learned enough at that point to know that the digits of pi are "random" (which I now know hasn't actually been proven...) but my friend said that it has to settle down at some point into some kind of repeating decimal or pattern. I said no, it doesn't, but he just couldn't wrap his head around the idea that pi was transcendental.
It's not a question of pi being transcendental. It's just a question of whether it's rational or irrational (ie. a real number that's not rational.) If it were rational, then it would at some point have an infinitely-repeating pattern (that can be expressed as the ratio between two integers.)
The square root of 2 is irrational (and therefore has no infinitely repeating pattern) but not transcendental.
Looking for the Z-order curve?
Granted, that's interleaving binary digits instead of decimals (thus resulting in a much more useful curve), but the curve is spacefilling in any base.
Proving that your function is indeed a bijection is easy.
Warp wrote:
This means that there is no one-to-one mapping between the set of natural numbers and the set of all possible combinations of natural numbers... which is very counter-intuitive.
Is it? All you have is a mapping of infinite elements from A to a single element form B. That's nowhere near a bijection, and is useless in constructing a bijection. Just because there's some kind of a relationship doesn't mean there's a bijection.
Warp wrote:
One would think that you could number each combination uniquely.
Why would you? Can you come up with an algorithm that would do so?
Does that work? Or is it ambiguous (ie. more than one point in the square would map to the same point on the unit line)?
I think it might be. Or am I wrong when I say that (0.4999..., 0.9999...) (which maps to 0.4999...) and (0.5, 0.0) (which maps to 0.5) map to the same point?
This means that there is no one-to-one mapping between the set of natural numbers and the set of all possible combinations of natural numbers... which is very counter-intuitive.
Is it? All you have is a mapping of infinite elements from A to a single element form B. That's nowhere near a bijection, and is useless in constructing a bijection. Just because there's some kind of a relationship doesn't mean there's a bijection.
What I mean is that it's counter-intuitive after you have fully accepted the fact that, for example, the set of rational numbers is as big as the set of natural numbers (ie. there is a one-to-one relationship between the two.)
As I commented in another post, the first intuition is that of course there are more rational numbers than natural numbers. However, that intuition is wrong. It takes some convincing before one's brain starts accepting that the two sets are of "equal size".
It's thus not strange at all that the same idea could be used to argue that the set of all possible combinations of decimal digits is as large as the set of natural numbers... except that that intuition would once again be wrong. It may be even harder to convince one's brain of this fact, especially after it has been convinced of the bijection between natural and rational numbers.
Scepheo wrote:
I think it might be. Or am I wrong when I say that (0.4999..., 0.9999...) (which maps to 0.4999...) and (0.5, 0.0) (which maps to 0.5) map to the same point?
You might have a point there. (Although I think that 0.9999... is exactly the same as 1.)
I think it might be. Or am I wrong when I say that (0.4999..., 0.9999...) (which maps to 0.4999...) and (0.5, 0.0) (which maps to 0.5) map to the same point?
Well, many numbers have two decimal representations. You'll have to agree which one to use in your function, otherwise you'll have up to four different function values for each set of (x, y) coordinates, and your function stops being a function.
f(0.5, 0.5) = 0.55
f(0.5, 0.5) = 0.4499999999
f(0.5, 0.5) = 0.5409090909
f(0.5, 0.5) = 0.4590909090
pick one and stick to it. I suggest the first, if you value your sanity in the upcoming proofs. ;)
Warp wrote:
What I mean is that it's counter-intuitive[..]
Maybe your intuition just sucks ;)
After learning about countability, whenever you encounter a new infinite set, your newly trained intuition should kick in and ask: "So how would I number these elements without missing any?". If you can't come up with a numbering off the top of your head, it's probably uncountable.
Until you retrain your intuition to do so (maybe Pavlov can help), your intuition will keep getting wrong results. Don't rely on the part of your brain made for counting apples to understand advanced math.
Warp wrote:
I came across an aptitude test for would-be computer science students and found an interesting question (which I could not solve at the time of writing):
Task L2
Time: 20 minutes
Find two natural numbers in ]1;100[.
Two persons, "Mr. Product", who knows the product of both numbers, and "Mr. Sum", who knows their sum, are having a talk:
Mr. Product: "I know neither of both numbers."
Mr. Sum: "I, too, know neither of both numbers; but I knew that you wouldn't know them."
Mr. Product: "Now I know both numbers."
Mr. Sum: "Now I know both numbers as well."
What two numbers are they talking about (only one answer is correct)?
A. 3 and 5
B. 2 and 7
C. 8 and 11
D. 4 and 13
Solution: Answer D is correct.
Source: English translation of Task L2 from http://www.pms.ifi.lmu.de/eignungstest/
Edit: Answer A is easily ruled out. Assume the correct answer was A then Mr. Product would know "15" and Mr. Sum "8".
Now for Mr. Sum there are 2 valid combinations of how to get to "8" by summing two natural numbers: 2+6 and 3+5 (1+7 and 4+4 are invalid). The products of these are 2*6=12 and 3*5=15.
Mr. Product on the other hand knows 15, that can solely be written as 3*5. Mr. Product would hear Mr. Sum claim that he could not possibly know the numbers of which "15" is composed of, which is not true, since there is only one combination.
Edit 2: Mhh, the same is true for answer B. How can Mr. Sum be sure that Mr. Product wouldn't know the numbers only by having their sum and how can Mr. Product deduce from that what both numbers are? I am probably over-thinking this.
All syllogisms have three parts, therefore this is not a syllogism.
After learning about countability, whenever you encounter a new infinite set, your newly trained intuition should kick in and ask: "So how would I number these elements without missing any?". If you can't come up with a numbering off the top of your head, it's probably uncountable.
It's just that without experience it can be hard to come up with ways to enumerate an infinite set of values. This often even when there's a trivial (in hindsight) way.
For example, how to enumerate all rational numbers? It's surprisingly difficult to come up with a way. Yet, there's a very simple one: Put all rational numbers in order in an infinite two-dimensional grid, like this:
1/1 1/2 1/3 1/4 1/5 ...
2/1 2/2 2/3 2/4 2/5 ...
3/1 3/2 3/3 3/4 3/5 ...
...
and then simply enumerate them diagonally (ie. 1->1/1, 2->1/2, 3->2/1, 4->1/3, 5->2/2, 6->3/1, and so on.)
(This way also helps understanding why any set consisting of values formed from n integers each is likewise enumerable.)
I came across an aptitude test for would-be computer science students and found an interesting question (which I could not solve at the time of writing):
Task L2
Time: 20 minutes
Find two natural numbers in ]1;100[.
Two persons, "Mr. Product", who knows the product of both numbers, and "Mr. Sum", who knows their sum, are having a talk:
Mr. Product: "I know neither of both numbers."
Mr. Sum: "I, too, know neither of both numbers; but I knew that you wouldn't know them."
Mr. Product: "Now I know both numbers."
Mr. Sum: "Now I know both numbers as well."
What two numbers are they talking about (only one answer is correct)?
A. 3 and 5
B. 2 and 7
C. 8 and 11
D. 4 and 13
'Mr. Product: "I know neither of both numbers."'
So there is more than one factorization (not using 1) for the product.
This rules out A, as 15 can only be factorized as 3*5.
This rules out B, as 14 can only be factorized as 2*7.
Leaving C and D.
Mr. Sum: "I, too, know neither of both numbers; but I knew that you wouldn't know them."
So Mr. Sum's sum cannot be broken down in any way that has only one factorization.
Let's consider C. 8 and 11 add to 19. This can be broken down into:
2 and 17, product 34, only factorizable as 2*17
So in the world of C, Mr. Sum cannot claim this.
Let's consider D. 4 and 13 add up to 17. This can be broken down into:
2 and 15, product 30, factorizable as 2*15 or 6*5
3 and 14, product 42, factorizable as 6*7
4 and 13, product 52, factorizable as 2*26
5 and 12, product 60, factorizable as 10*6
6 and 11, product 66, factorizable as 3*22
7 and 10, product 70, factorizable as 14*5
8 and 9, product 72, factorizable as 24*3
Can you see? In the world of D, where Mr. Sum knows 17, Mr. Sum knows that whatever the two components are, it is AMBIGUOUS for Mr. Product as to what the factors are for him - so Mr. Sum knows already that Mr. Product could not know his numbers.
Mr. Product knows 52, which factorizes as 26*2 and as 13*4. If Mr. Sum had 26 and 2 23 and 5 is a unique factorization - so he would not have claimed Mr. Product could not know his numbers. So Mr. Sum must have 13 and 4. So now Mr. Product knows his numbers and declares this fact.
Mr. Sum knows 17. How did he figure out which one of his universes was correct (Mr. Product wouldn't have said he now knows both numbers in this universe)? I think this is just tedious elimination, try every 'Mr Product knew this number' universe and only 4 and 13 should work (haven't tried yet). We don't need to know it to determine D is the right answer at least.
[...]
Mr. Sum: "I, too, know neither of both numbers; but I knew that you wouldn't know them."
So Mr. Sum's sum cannot be broken down in any way that has only one factorization.
Let's consider C. 8 and 11 add to 19. This can be broken down into:
2 and 17, product 34, only factorizable as 2*17
So in the world of C, Mr. Sum cannot claim this.
[...]
Somehow I'm no convinced by how you exclude answer C: 8 and 11.
Mr. Sum knows: 19
Mr. Product knows: 88
Since there are three valid factorizations of 88 (2*44, 4*22, 8*11), Mr. Product's first claim is correct.
Mr. Sum can think of the following representations of 19:
2+17 (34)
3+16 (48)
4+15 (60)
5+14 (70)
6+13 (78)
7+12 (84)
8+11 (88)
9+10 (90)
While it is true, that 34 has only one factorization (2*17), like you wrote, 48 and others have multiple.
Mr. Sum however cannot be sure which of the above sums comprises his number 19, so if it was 3 and 16, then Mr. Product's product would be 48 which means that his first claim is still true (48 has more than one factorization).
Edit: Ugh. Scratch all of the above. This is about Mr. Sum knowing for sure Mr. Product could never guess the factors of his product, which isn't true as long as there's a single pair of summands for Mr. Sum's number, whose factorization of their product reveals there's only one possible combination.
All syllogisms have three parts, therefore this is not a syllogism.
Hm. I misread "]1;100[" as "[1,100]", "between 1 and 100 inclusive". I didn't know it was supposed to be "(1,100)", "strictly between 1 and 100".
I have never seen the notation "]1;100[" before.
About there being exactly one right answer, the statement of L2 in German does somewhat imply that there is exactly one right answer, but strangely the boxes are all check boxes, and almost none of the questions have exactly one right answer (as in, your answer is supposed to be a subset of the set of given choices).
So if it was open ended, without giving us the 2 numbers, we'd have to find some numbers x0 and y0, such that:
-Their product, P=x0y0, has more than one factorisation in (1,100). P=x0y0=x1y1=.....=xnyn
-For all xi and yi , let Si=xi+yi be their sum. For each different j'th pairing of this sum, say Si=aij+bij, it has the property that each hypothesised product Pij=aijbij has more than one factorisation, for all i=/=0. That is to say in all others, there exists a k such that aik and bik are both prime. thus Pik=aikbik has only one factorisation.
First axiom makes sure Mr.Product won't know for sure what his numbers are, as there is more than one factorisation. Second axiom covers all potential S Mr.Sum could have, given what P is. It makes sure that only one of these sums, IE only one factorisation of P, has the property that all hypothesised products Pij has more than one factorisation for all j; and thus there's only one value of Si=S0 which enables Mr.Sum to say "Mr.Product cannot know for sure what his factors are".
This information when passed onto Mr.Product, immediately identifies the value of Si for him, being the only one where Pij all have more than one factorisation. This was defined as So=xo+yo, as all other values of Si may or may not have a product which has more than one factorisation. Applying this to the example:
P=52
52=4x13=x0y0
52=2x26=x1y1
S0=x0+y0=17
S1=x1+y1=28
For S0=17
17=15+2=a01+b01, P01=a01b01=15x2=6x5
17=14+3=a02+b02, P02=a02b02=14x3=6x7
17=13+4=a03+b03, P03=a03b03=13x4=2x26
17=12+5=a04+b04, P04=a04b04=12x5=6x10
17=11+6=a05+b05, P05=a05b05=11x6=22x3
17=10+7=a06+b06, P06=a06b06=10x7=35x2
17=09+8=a07+b07, P07=a07b07=09x8=18x4
For S1=28
28=26+2=a10+b10, P10=a10b10=26x2=13x4
28=25+3=a11+b11
28=24+4=a12+b12
28=23+5=a13+b13, P13=a13b13=23x5
(plus more but not neccessary)
But we have P13=23x5=115, which has only one factorisation, thus if Mr Sum had S=S1=28, this case would falsify the "I know you don't know your factors" logic from Mr Sum, thus Mr.Product can infer we have S=S0=4x13. This tells Mr.Product his answer at least, but you still need to show how Mr.Sum now knows them too, which would require tonnes more algebra, a 4th or 5th subscript on potential sums/products, and maybe an extra axiom or two. Just go ask Mr.Answer in future...
The sieve or Eratosthenes is a relatively simple algorithm for finding all the prime numbers smaller than a given value. Basically it works by starting from 2 and marking all of its multiples as composite, then advancing to the next unmarked number and marking all of its multiples as composite and so on.
A small optimization can be performed in that when advancing to the next unmarked number, you can stop at the square root of the maximum value. The reason for this is relatively easy to understand intuitively: By necessity, every single composite number within the range will have at least one prime factor that's smaller or equal to the square root of the maximum value. Therefore once you get to this value, all composites will necessarily have been marked so there's no need to continue from there.
A less intuitive optimization is that when marking the multiples of the current value, you don't have to start from its first multiple. Instead, you can start from its square. The algorithm can be written in code eg. like this:
Language: cpp
prime.set();
for(unsigned long n = 2; n*n < kMaxValue; ++n)
if(prime[n])
for(unsigned long index = n*n; index < kMaxValue; index += n)
prime[index] = false;
(Note how the outer loop ends at the square root of kMaxValue, and the inner loop starts at the square of the current prime we are marking all multiples of.)
So my question is: Why can you start marking multiples from the square of the current value?
You do that for the same reason that you only go until the square root of the maximum value. When you start processing prime p, you have already processed all primes smaller than p. Any unmarked composite number n = r*s will have r and s greater than or equal to p. So, n is at least p². Because of that, the sieve is already correct for all values less than p².
Further optimizations can be applied, you can initialize all even numbers except 2 as composite and , start at 3 and use n+=2 instead of ++n, and that can be made even better using something called a factorization wheel, but that's more complicated.
I was wondering: What's the smallest rectangle you can completely fill with tetrominoes so that no two equal tetrominoes touch each other?
(Let's skip the two trivial solutions and require two or more tetrominoes)
Wikipedia shows a solution to a different tiling problem, but by removing the rightmost 4x1 tile it yields a solution to mine with 4x9:
Unfortunately, I couldn't find anything smaller. The corners are tricky. Are you more lucky? Otherwise I'll probably try to write a small program over the weekend.
And I'm aware there's a lot of stuff on tetromino tiling on the net, but I couldn't find anything matching my specific problem.
The intersection of the "square chords" are at 90° angles. As t increases, the intersection marked with the right angle sign traces the arc of a circle where the bottom edge of the square is a diameter for the circle. (If there are three points A,B,C on a circle and angle ACB is 90°, then AB forms a diameter for the circle.)
Thus, assuming the square's vertices are at (0,0), (0,1), (1,0) and (1,1), the marked intersection is at (0.5 + 0.5 cos(2t) , 0.5 sin(2t)). Or, in polar coordinates, (cos(t),t), where t functions as θ and r=cos(θ).
Edit: The distance from the bottom-left corner to the marked intersection is cos(t) and the distance from the bottom-right corner to the same is sin(t). That means the inner square has side length |cos(t)-sin(t)| and its area is (cos(t)-sin(t))²=1-sin(2t).
