The answer's not huge (well less than 1000000). Looking at my code, I pretty much did a brute force approach. I didn't have a particularly efficient prime sieve and it finished in under 5 seconds.

(Reply) (Thread)

I did it using SQL, with a table as my 'scratch pad' (one row per integer until I find a counterexample, but with extra fields to keep track of things to make the comparisons faster).

The answer is less than ten thousand but more than one thousand (unless I made a mistake, that is - I didn't register so I can't check the answer).

This is the only one I've done, because you asked about it and it seemed like something I could do quickly with SQL.

(Reply) (Thread)

I'd like to see your SQL.

(Reply) (Parent) (Thread)

create table #number_list
(numval int, 
isodd bit, 
isprime bit, 
isdoublesquare bit)

delete #number_list

declare @working int
declare @finished bit
declare @isodd bit
declare @isprime bit

select @working = 0, @finished = 0



while @finished = 0
begin 
	select @working = @working + 1

	select @isodd = case when @working % 2 = 0 then 0 else 1 end, 
		@isprime = case when exists (select * from #number_list
			where #number_list.isprime = 1 
			and #number_list.numval > 1
			and @working % #number_list.numval = 0) then 0 else 1 end



	if @isodd = 1 and @isprime = 0 
	 and not exists (select @working, nl1.numval, nl2.numval
		from #number_list nl1
		cross join #number_list nl2
		where nl1.isprime = 1
		and nl2.isdoublesquare = 1
		and nl1.numval + nl2.numval = @working)
	  begin 
		select 'couldn''t break down ' + convert(varchar, @working)
		 select @finished = 1
	  end
	else
	insert #number_list
	select @working, @isodd, @isprime, 
		case when exists (select * from #number_list
			where @working = #number_list.numval * #number_list.numval * 2) then 1 else 0 end

	
end 

(Reply) (Parent) (Thread)

Clearly I'm an SQL tyro. Can you explain what's going on in this code?

(Reply) (Parent) (Thread)

First I'm creating a table with four columns and no rows. I'm going to add a row to this table for every integer, starting at 1, until I find a counterexample to the conjecture. So when I'm examining the number 158 to see whether it's a counterexample, the table contains one row for each integer from 1 to 157, and it will grow as I proceed.

Each row in the table contains an integer (numval), along with three flags to indicate whether that integer is odd, prime and/or a double-of-a-square.

The line "delete #number_list" is unnecessary. It removes all the rows from that table but it's empty at the moment since it's just been created. I had it in my script because I was running it repeatedly while debugging and needed to empty it out each time I ran it (because I wasn't dropping and recreating the table). So just ignore that.

I declare four variables (beginning with @). @finished is a flag that indicates whether I've found my counterexample. @working is the latest integer that I'm looking at, and I start looping. Note that this dialect of SQL doesn't include a "boolean" type so I'm using bit variables, with 1 for "true" and 0 for "false".

On each loop I increase @working by one but I don't add a row to the table for it yet.

I examine @working to see whether it's odd (using the % modulus operator) and whether it's prime (by asking whether there are any rows in the table that are prime and divide evenly into @working). The "exists" function takes a SQL query as input and returns a true/false indicating whether that SQL query returns any results. So if running that query would produce one or more divisors, "exists" returns a "true" value, which the "case" statement converts into a 1.

Next, if @working is an odd composite (that is, odd and not prime), I want to check it to see whether it's the counterexample I'm looking for. To do that I ask whether there are two numbers in the list such that the first is prime and the second is the double of a square, such that they add up to equal @working. The "cross join" means that I'm taking the Cartesian product of two copies of the table, in other words looking at all possible combinations of numbers from the table. This could be done more efficiently using a real inner join, like so:

select nl1.numval, nl2.numval
from #number_list nl1
join #number_list nl2 on nl.numval + nl2.numval = @working
where nl1.isprime = 1
and nl2.isdoublesquare = 1

Anyway, if such a pair does not exist, then I've found the answer (so I announce it by reporting its value back to the console and bailing out of the loop); otherwise @working is not a counterexample and I add its information to the #number_list table ... and then we loop around again with the next integer.

In retrospect I should be dealing more cleverly with the squares-of-doubles by declaring local variables to keep track of the next square-of-doubles that's higher than @working, along with the integer that spawned it, and every time I hit the next square-of-double I increment by one the integer that spawned it, calculate the double of its square, and watch for that to appear. This would eliminate the need to ask "are there any numbers in the list such that doubling their squares equals @working" every time, which takes longer and longer each time because it has to scan the table, which is growing. This is the final "exists" query in the code and it is inefficient because the squares-of-doubles increase monotonically and it's easy to keep track of them and identify them as they come up if you're alert.

I'm not familiar with the expression "tyro". All it gives me is an image of you in Tyrolean costume. But looking it up on Wikipedia refers me to "tiro", Latin for "beginner". Didn't know that one.

Edited at 2008-03-15 02:04 pm (UTC)

(Reply) (Parent) (Thread)

Thanks! Very interesting. And yes, "tyro" is not just Latin—Merriam-Webster says "a beginner in learning : novice". I think I learned it from reading Master of the Five Magics, or something like it, back in high school.

(Reply) (Parent) (Thread)

also it looks like the "isodd" field in the working table is useless; I never refer to it. So it should be removed.

(Reply) (Parent) (Thread)

And another thing: strictly speaking this isn't SQL, which is just a specification for querying tables and getting result sets. This is T-SQL, Microsoft's version of a procedural programming language based on SQL. So T-SQL includes things like "while" loops and declaring variables and evaluating "if" statements and declaring your own subroutines and so on.

Oracle's version of this is called PL/SQL and looks very similar. Microsoft's version is virtually the same as Sybase's. I have no idea what goes on in the non-borg versions of SQL like MySQL and whatnot.

(Reply) (Parent) (Thread)

Ah, yeah, I thought it looked weird for SQL. I'm only familiar with PostgreSQL, which has its own language, PL/pgSQL, but I've never looked into it. I don't even use the "psql" shell—I use the spgsql package for PLT Scheme.

(Reply) (Parent) (Thread)

Could one of you (or anybody else) email me the answer directly to avoid it being posted and searchable by google. My email is aarondf@bu.edu

I have a file with what I think is every odd composite (unless I don't understand the definition) up to 1 million with an answer (doubled square and prime summing to it) that seems completely legit. Really don't have a clue what I could be doing wrong on this.

(Reply) (Thread)

Thanks Bill.

Turns out I didn't understand the definition of "odd composite" (partly from unwisely trying to look it up as that string rather than looking up Composite and applying odd to it). I found a definition that had the same first 6 values as given on the PE page but later on diverged and ended up missing the answer number. Using my definition, there wasn't one till at least 1 billion.

Anyway, annoying but glad it is solved and wasn't my code that was the problem.

(Reply) (Parent) (Thread)

I just did it, but it took me a while to remember how to do streams in Scheme and I see others have already helped you. Interestingly, the first two counterexamples are close to each other (and relatively small), but I haven't found a third counterexample yet.

(Reply) (Thread)

Looks like Mathematica will do nicely on these. Here's a program written in 5 minutes, which checks all odds up to 100,000 in about 3 seconds, returning 2 solutions:


Do[
i = 0;
While[(PrimeQ[(2*n+1) - 2*i*i] == False && i*i < n), i = i+1];
If[i*i > n-2, Print[2*n+1]];,
{n, 4, 50000}]

(Reply) (Thread)

The site also has statistics on languages people are using for it, including a pencil/paper category. Kind of interesting. SQL isn't listed at all Bill.

My problem turned out purely to be a misunderstanding of what an "odd composite" was. Can't find it now but found a site which seemed to say they were numbers of the form 3+(N*6) and/or 5+(N*10) for all N 1..INF. This happens to match the 6 examples given on the site but eventually diverges (think 49 is the first one which should be included in the real definition and this doesn't include). Think you would find if you used this definition, the conjecture might hold forever and certainly holds for a VERY long time. And yes, btw, I did find the above a weird definition but I had never heard the term before.

(Reply) (Thread)

SQL isn't listed at all Bill

Doesn't surprise me at all. It's just that I was doing some complex SQL coding today and so it was a case of having a hammer in my hand and seeing your problem as a nail and I decided to see how it would work out. I could just as easily have written a crude brute-force looper in VB or C to add up primes and doubles of squares and do a sieve-of-aritosthenes until something wasn't covered. No way am I saying SQL is the best approach. Just something I was fooling around with.

(Reply) (Parent) (Thread)

I haven't done these problems at Project Euler, but it looks better for what you are doing than what I have to offer. As for other sites:

http://www.pythonchallenge.com/
The Python Challenge is one of those URL-changing riddle trails, but designed to have you writing Python programs to solve the problems. With a couple exceptions well advertised, there is nothing that really requires the language used be Python. It starts out OK, but it gets very puzzly and for some reason ends up with a lot of image manipulation stuff (intended for use with Python Imaging Library) in the later levels. I completed this one a few years ago; it has 33 levels.

http://icpcres.ecs.baylor.edu/onlinejudge/
This one is more in the style of a programming contest, with programs in C, C++, Java, or Pascal to be graded by being tested with some unknown data meeting given specifications. So it does not have the very simple "Hello, World" style problems, but there is a great range of difficulty beyond that.

There are more programming problems here than you will likely ever solve. If your language is NOT of these four, you won't be able to use the online judge, so you won't be able to check your answers, but it can still give you ideas of programs to try to write.

They've moved recently, and the new site isn't complete yet, in particular with no useful instructions. If you go into any of the problem sets, find a problem you want to do, click on the submit icon above the problem and submit your program in one of those languages to be checked.

(Reply) (Thread)