This is the (orthogonal projection of the) front view of a polyhedron:
The left, right, up, down and back views are identical to that. Draw the polyhedron from a different angle (that makes clear what its shape is).
Note that no two adjacent faces are parallel.
Wolfram Alpha is wrong. The volume is not 1/(3√2), regardless if unit edge length means the side length of the large tetrahedron that is intersected with its dual (volume is √2/8), or unit edge length means the side length of the tetrahedra extending out from the octahedron (volume is √2).
What's the volume if the unit length is the length of the side of the cube that contains the stellated octahedron (iow. the side length of the square I posted, ie. the distance between the tips of two adjacent "spikes", ie. the height of the polyhedron when it's on the floor like on the rendering I posted)?
Or in other words, how much of the volume of the containing cube does the stellated octahedron take?
Wolfram Alpha is wrong. The volume is not 1/(3√2), regardless if unit edge length means the side length of the large tetrahedron that is intersected with its dual (volume is √2/8), or unit edge length means the side length of the tetrahedra extending out from the octahedron (volume is √2).
Huh, that's weird, using Google's formula for the volume of a tetrahedon, I tried taking two tetrahedrons and subtracting their intersection, which gave me 5/(16√2) and is equivalent to your first case (which you said was √2/8). If I, however, take it as the length of the protruding tetrahedra, it gives me (2√2)/3, not √2 ...
If I, however, take it as the length of the protruding tetrahedra, it gives me (2√2)/3, not √2 ...
That's just the volume of the 8 protruding tetrahedra. The volume of the octahedron (whose edge length is also 1) is √2/3; add it to the volume of the 8 tetrahedra to get √2.
Warp wrote:
What's the volume if the unit length is the length of the side of the cube that contains the stellated octahedron (iow. the side length of the square I posted, ie. the distance between the tips of two adjacent "spikes", ie. the height of the polyhedron when it's on the floor like on the rendering I posted)?
If the length between the tips of two adjacent spikes is 1, then the length of an edge of a protruding tetrahedron is √2/2 (think of two adjacent spikes at (1/2,1/2,1/2) and (1/2,1/2,-1/2), and a corner where the respective tetrahedra meet which is at (1/2,0,0)). Since the volume of a stellated octahedron where the unit length is the edge of a protruding tetrahedron is √2, then the volume of this stellated octahedron is √2 (√2/2)3=4/8=1/2. So, the stellated octahedron takes up half of the volume of the cube it is contained in.
Now that Warp suggested it, there is actually another way to compute the volume. The stellated octahedron is a cube with (non-regular) tetrahedra cut out from each of its edges. If the cube has unit side length, then each of the tetrahedra cut out clearly has base area 1/4 and height 1/2, and so the volume cut out by each one is (1/3)(1/4)(1/2)=1/24. Since 12 of them are cut out, a total volume of 12(1/24)=1/2 is cut out of the cube, leaving a remaining volume of 1-1/2=1/2.
That's just the volume of the 8 protruding tetrahedra. The volume of the octahedron (whose edge length is also 1) is √2/3; add it to the volume of the 8 tetrahedra to get √2.
Ah, I don't know where my head was. I forgot to account for the fact that the intersection is an octahedron in the first case and that there is an intersection in the second case. Silly me. Thanks for the explanation, though.
Bisqwit noticed something about the divisibility of numbers of the form 2x*y-1, where x is an integer > 0 and y is an integer constant, so out of curiosity I investigated a bit further and noticed that (although with the caveat that I only tested with 64-bit integers, so there's room for error):
All 2x*2-1 are divisible by 3.
All 2x*3-1 are divisible by 7.
All 2x*5-1 are divisible by 31.
All 2x*7-1 are divisible by 127.
All 2x*13-1 are divisible by 8191.
All 2x*17-1 are divisible by 131071.
All 2x*19-1 are divisible by 524287.
Moreover:
Only numbers where y is a prime have a divisor that's different from all previous divisors.
All numbers of that form where y is even are divisible by 3. All such numbers where y is a multiple of 3 (and not even) are divisible by 7. All such numbers where y is a multiple of 5 (and not divisible by either 2 or 3) are divisible by 31. And so on.
All those divisors seem to be prime. Moreover (and this is only a conjecture because of the limits of 64-bit arithmetic), it seems that the divisors always increase, and they seem to themselves by of the form 2z-1 where z is a prime.
Even more curiously, the z in that formula is the same as the y in the original numbers
2x*2-1 are divisible by 3; 3 = 22-1
2x*3-1 are divisible by 7; 7 = 23-1
2x*5-1 are divisible by 31; 31 = 25-1
2x*7-1 are divisible by 127; 127 = 27-1
2x*13-1 are divisible by 8191; 8191 = 213-1
2x*17-1 are divisible by 131071; 131071 = 217-1
etc.
Thus a conjecture can be formulated from the above:
All numbers of the form 2x*y-1, where x and y are integers, x>0 and y is prime, are divisible by 2y-1.
I don't know, however, if it's reasonable to conjecture that 2y-1 is always prime (because it would always be a Mersenne prime, which seems unlikely).
Edit: I actually noticed that I inadvertently skipped a crucial value:
All 2x*11-1 are divisible by 23.
There doesn't seem to be a clear connection between 11 and 23. I suppose the conjecture holds for Mersenne primes, but not others.
However, it could still be conjectured that the divisor itself is always prime. Its form is more complex than simply 2y-1, though.
Bisqwit noticed something about the divisibility of numbers of the form 2x*y-1, where x is an integer > 0 and y is an integer constant, so out of curiosity I investigated a bit further and noticed that (although with the caveat that I only tested with 64-bit integers, so there's room for error):
...
Interesting, I'll write a Haskell program for this when I'm home as an exercise and edit this post with results for higher numbers.
Edit: Doh, let me get home first. Now you took all my motivation. I admit, this may be in part because the weekend started.
All syllogisms have three parts, therefore this is not a syllogism.
This is more simple than it looks. Just rearranging the power, and taking 22x-1 modulo 3, we have
22x-1=(22)x-1=(4)x-1≡(1)x-1≡1-1≡0
Hence 3 divides 22x-1. Similarly for the other numbers
23x-1=(23)x-1=(8)x-1≡(1)x-1≡0 Mod 7
25x-1=(25)x-1=(32)x-1≡(1)x-1≡0 Mod 31
27x-1=(27)x-1=(128)x-1≡(1)x-1≡0 Mod 127
213x-1=(213)x-1=(8192)x-1≡(1)x-1≡0 Mod 8191
217x-1=(217)x-1=(131072)x-1≡(1)x-1≡0 Mod 131071
219x-1=(219)x-1=(524288)x-1≡(1)x-1≡0 Mod 524287
Or more generally, just taking the numbers inside, then going modulo (2p-1) in order to reduce this value to 1, gives
2x*p-1=(2p)x-1≡(1)x-1≡0 mod (2p-1).
Hence (2p-1) divides (2x*p-1).
This works for all p, even for values not prime. EG 2x*4-1 will be divisible by 24-1=16-1=15. Now this itself is a composite number, but since composite numbers have prime factors it immediately follows that there exists a prime (3 or 5 here) which divides this expression.
Now, for the case P=11, that's not an exception, it's just that you're choosing to focus on the wrong information. We have 211-1=2048-1=2047. So the formula predicts it will be divisible by 2047, but since this is a composite number, we have 2047=23*89 then it is also true to say it is always divisible by 23 (or 89) as well.
So there always exists a prime which divides every term in such a sequence.
More generally,
an - 1 = (a-1)*(an-1 + an-2 + an - 3 + ... + a2 + a + 1)
Proof: fix a and use mathematical induction over n.
So, make a = 2y and n = x, like Flip did.
pff you don't need to proove that complicated thing.
It's much easier.
You must know well known property:
(a*b) mod c = (a mod c)*(b mod c)
proof:
a = u*c + (a mod c) (select right u)
b = v*c + (b mod c) (select right v)
then
(a*b) = (u*c + (a mod c))*(v*c + (b mod c))
rearrange
a*b = u*v*c*c + ((a mod c)+(a mod c))*v*c + (a mod c)*(a mod c)
remove all what is multiplied by c and you'll get (a*b) mod c.
so you can always use (a mod c) instead of a.
a^x - 1 = 0 (mod b)
a^x = 1 (mod b)
(a mod b)^x = 1 (mod b)
your question is: what b I need to pick, so it would work for any x?
It must work for x = 1, so you need to pick any such b:
(a mod b) = 1 (mod b)
in other words
a = 1 (mod b)
also if it's so, then
(a^x) = 1 (mod b)
because
((a mod b)^x) = (1^x) = 1 (mod b)
how many of such b?
a = 1 (mod b)
a - 1 = 0 (mod b)
in other words, a - 1 must be devisible by b.
a^x - 1 divisible by b for any x if and only if (a-1) divisible by b.
So, factorize (a-1) and make all combinations of factors: you'll get all such b.
Is there any way to get Fermat's little theorem out of this? (Fermat's little theorem states that if p is prime, a^p - a is a multiple of p).
I don't think so. The previous problem is just a matter of simplification and doesn't depend on the primality of any of the numbers.
Warp wrote:
Thus a conjecture can be formulated from the above:
All numbers of the form 2x*y-1, where x and y are integers, x>0 and y is prime, are divisible by 2y-1.
This works for all integers x and y, even if y is not prime.
2x*y - 1 ≡ (2y)x - 1 ≡ (2y - 1) * ( (2y)x-1 + (2y)x-2 + ... + (2y)2 + (2y)1 + 1 )
This last identity comes from the sum of the terms of a geometric progression.
Therefore, 2x*y - 1 is multiple of 2y - 1.
Warp wrote:
All 2x*11-1 are divisible by 23.
There doesn't seem to be a clear connection between 11 and 23. I suppose the conjecture holds for Mersenne primes, but not others.
However, it could still be conjectured that the divisor itself is always prime. Its form is more complex than simply 2y-1, though.
In this case, 2x*11 - 1 = (211)x - 1 = 2048x - 1 = (2048-1) * something = 2047 * something
As 2047 = 23*89, then 23 divides 2x*11 - 1 for all x.
I was thinking whether a problem like this is provably unsolvable, or simply extremely hard:
"What is the smallest positive integer that cannot be computed with a C++ program of at most 1000 characters?"
(Note that this doesn't mean that there aren't larger integers than the answer that can't be computed by such a program. The problem is asking for the smallest positive integer that cannot be, even if there exist larger ones that can.)
I know this is (probably) related to Kolmogorov complexity, but that subject is a bit too complex for my knowledge. (Also, I'm not sure if the concept of Kolmogorov complexity actually answers my question, ie. whether that problem is unsolvable or just very hard.)
I was thinking whether a problem like this is provably unsolvable, or simply extremely hard:
"What is the smallest positive integer that cannot be computed with a C++ program of at most 1000 characters?"
(Note that this doesn't mean that there aren't larger integers than the answer that can't be computed by such a program. The problem is asking for the smallest positive integer that cannot be, even if there exist larger ones that can.)
I know this is (probably) related to Kolmogorov complexity, but that subject is a bit too complex for my knowledge. (Also, I'm not sure if the concept of Kolmogorov complexity actually answers my question, ie. whether that problem is unsolvable or just very hard.)
Since, for starters, all ~1000 digit numbers are computable under that criterion, I imagine the answer is very large. To throw out a guess, perhaps one million or so digits.
Since, for starters, all ~1000 digit numbers are computable under that criterion, I imagine the answer is very large. To throw out a guess, perhaps one million or so digits.
I'm not asking what the number is (because it's practically, perhaps even provably, impossible to calculate). I'm asking whether the problem is unsolvable or simply very hard.
One could naively think "it's not unsolvable; simply go through every possible valid C++ program of 1000 characters or less, and for each one see which numbers it outputs, if any". However, that method might not be usable because you may encounter the halting problem: You cannot know if a given program will ever halt.
Of course the halting problem is related to programs of any arbitrary size. Here we are talking about programs of a limited size, so perhaps the halting problem doesn't apply? Perhaps it's possible to simply list which programs halt and which won't?
Of course then there's the problem of programs that don't halt but do print numbers. If they just keep printing numbers, can you ever find out which ones?
An unbounded version of the problem is probably unsolvable. In other words, if we modify the problem like this:
"For any given n, what is the smallest positive integer that's not computable by a C++ program of at most n characters?"
Here we probably stumble across the halting problem outright.
I forgot to mention that, obviously, for the problem to make sense, the program has to be a terminating one. In other words, there has to be an ending condition. (Else it could simply print increasing integers forever.)
An interesting variant of the problem is this:
"What is the largest integer that can be computed by a terminating C++ program of at most 1000 characters?"
The condition that the program must terminate actually puts an upper limit to how big the computer number can be. Since the program has a limited size, the computed number also must have a limited size.
Thus the core question is whether this problem is unsolvable or just very hard.
Since, for starters, all ~1000 digit numbers are computable under that criterion, I imagine the answer is very large. To throw out a guess, perhaps one million or so digits.
I'm not asking what the number is (because it's practically, perhaps even provably, impossible to calculate). I'm asking whether the problem is unsolvable or simply very hard.
One could naively think "it's not unsolvable; simply go through every possible valid C++ program of 1000 characters or less, and for each one see which numbers it outputs, if any". However, that method might not be usable because you may encounter the halting problem: You cannot know if a given program will ever halt.
Of course the halting problem is related to programs of any arbitrary size. Here we are talking about programs of a limited size, so perhaps the halting problem doesn't apply? Perhaps it's possible to simply list which programs halt and which won't?
Of course then there's the problem of programs that don't halt but do print numbers. If they just keep printing numbers, can you ever find out which ones?
An unbounded version of the problem is probably unsolvable. In other words, if we modify the problem like this:
"For any given n, what is the smallest positive integer that's not computable by a C++ program of at most n characters?"
Here we probably stumble across the halting problem outright.
Ah, I see. I think you're right, however, that we could simply list all programs with 1000 or fewer characters and analyze whether they halt or not. I see no reason why that shouldn't be possible. Then, as you say, just look at the numbers output. (I assume you're talking about programs that output one number. We would want to disallow, for example, while true do print i; i++; end. Excuse my pseudocode.)
I think it is interesting that this seems to imply that the halting problem is solvable for any program of finite length. It's only when you allow programs of infinite length (which are physically unrealizable) that you run into problems.
Any experts on this topic?
It is definitely possible to take any arbitrary program and analyze it so see if it halts or not; the halting problem is that there is no algorithm to determine this. Programs of infinite length aren't necessary for that.
So while, to me, it seems "possible" to analyze all programs of length N and determine whether they halt and if so, what number they output, the halting problem means that you can't do this algoritmically.
In other words, I think the answer to Warp's question is "simply extremely hard".
It is definitely possible to take any arbitrary program and analyze it so see if it halts or not; the halting problem is that there is no algorithm to determine this. Programs of infinite length aren't necessary for that.
So while, to me, it seems "possible" to analyze all programs of length N and determine whether they halt and if so, what number they output, the halting problem means that you can't do this algoritmically.
In other words, I think the answer to Warp's question is "simply extremely hard".
Yeah, but what is the human thought process (as it applies to analyzing halting problem) other than an extremely complex algorithm? I'm not convinced that our thinking "transcends algorithms" and so the distinction is irrelevant.
I agree with your answer, however.
The left, right, up, down and back views are identical to that. Draw the polyhedron from a different angle (that makes clear what its shape is).
Note that no two adjacent faces are parallel.
