October 2, 2011 at 10:29 pm
Comments posted to this topic are about the item Conversion of a plain English problem into T-SQL
October 3, 2011 at 1:24 am
Thanks for that - some interesting points. I suspect that this is the modus operandii for a lot of people. It is when the problem space gets too large and complex that we need some of the more formalised structures to help manage the project.
October 3, 2011 at 1:31 am
I do realize this was not the purpose of the article but it made me think of it so here's a recursive version. It'll stop after 100 recursions unless the maxrecursion option is changed of course.
DECLARE @Start BIGINT;
SET @Start = 10;
WITH cte AS (
SELECT @Start [Value]
UNION ALL
SELECT CASE [Value] % 2 WHEN 0 THEN [Value] / 2 ELSE ([Value] * 3) + 1 END
FROM [cte]
WHERE CASE [Value] % 2 WHEN 0 THEN [Value] / 2 ELSE ([Value] * 3) + 1 END != 1
)
SELECT *
FROM [cte];
October 3, 2011 at 2:00 am
matt.bowler (10/3/2011)
It is when the problem space gets too large and complex that we need some of the more formalised structures to help manage the project.
Yep, agreed. This approach is probably best used by one person working on one thing at a time. I would imagine that using this approach on a large project would result in a fair old mess.
That said, I do recall times when I have used this approach to prototype some of the individual components before starting a larger project to help confirm that the project was viable. Also I found that the prototypes were a handy reference point for isolating and troubleshooting problems in the larger project once the build started.
Thanks for the comment, much appreciated.
October 3, 2011 at 2:04 am
dennis.hafstrom (10/3/2011)
I do realize this was not the purpose of the article but it made me think of it so here's a recursive version.
nice 🙂
October 3, 2011 at 3:10 am
might find this interesting...
IF OBJECT_ID('dbo.fn_TestCollatzConjecture') > 0
DROP FUNCTION dbo.fn_TestCollatzConjecture
GO
CREATE FUNCTION dbo.fn_TestCollatzConjecture ( @StartNumber BIGINT )
RETURNS VARCHAR(200)
AS
BEGIN
DECLARE @min-2 BIGINT
DECLARE @Levels INT
DECLARE @max-2 BIGINT
DECLARE @Ret VARCHAR(200) ;
WITH ApplyCollatzTransform
AS ( SELECT @StartNumber AS NewNumber ,
0 AS Level
UNION ALL
SELECT CASE WHEN NewNumber % 2 = 0
THEN NewNumber / 2
ELSE ( NewNumber * 3 ) + 1
END ,
Level + 1
FROM ApplyCollatzTransform ACT
WHERE NewNumber > 1
)
SELECT @min-2 = MIN(NewNumber) ,
@Levels = MAX(Level) ,
@max-2 = MAX(NewNumber)
FROM ApplyCollatzTransform
OPTION ( MAXRECURSION 0 )
IF @min-2 = 1
SET @Ret = 'Reached 1 after ' + CONVERT(VARCHAR(20), @Levels)
+ ' Level(s). Hit Max of ' + CONVERT(VARCHAR(20), @max-2)
+ ' before getting there...'
ELSE
SET @Ret = 'Did not hit 1 after ' + CONVERT(VARCHAR(20), @Levels)
+ ' Level(s)... Giving up...'
RETURN @Ret
END
go
DECLARE @StartNumber BIGINT
SET @StartNumber = 27
SELECT dbo.fn_TestCollatzConjecture(@StartNumber)
October 3, 2011 at 7:36 am
ABHILASH DHONGDI (10/3/2011)
might find this interesting...
IF OBJECT_ID('dbo.fn_TestCollatzConjecture') > 0DROP FUNCTION dbo.fn_TestCollatzConjecture
etc...
most impressive abhilash, thanks. just to be curious, did you write it using the approach i suggested? or was it written line by line as we see it now?
October 3, 2011 at 8:09 am
With regards to your discussion of the iterative process of building the code, one step I didn't see was how to stop the infinite loop if the Collatz Conjecture does NOT reach the value of 1! In the generic sense, this would be the error-catching phase of the development of the code.
p.s. ABHILASH DHONGDI - Clever use of MAXRECURSION 0! Nicely done!
October 3, 2011 at 8:13 am
My comment conveniently ignores the
one of the things I am interested in is the count of how many repetitions of the sequence it took to reach 1
but I enjoyed the problem/solution and wanted to comment so, hey ...
Because the tool we're using to solve this poser is SQL, I'd like to see the solution 'learning' about numbers that it knows will eventually reach 1 and therefore cutting corners. So I'd INSERT into a ProvedNumbers table once I hit 1 or hit a number that was already in ProvedNumbers.
e.g. I've learned that 8 goes 4, then 2, then 1. So when I tackle 10 I can stop at 10,5,16,8 and add 10 to ProvedNumbers. This will then help when I do 12 and 13 and they reach 10.
Rob - I look forward to the product of more "particularly idle evenings" !
Jamie.
Isle of Man
October 3, 2011 at 8:33 am
Carla Wilson-484785 (10/3/2011)
With regards to your discussion of the iterative process of building the code, one step I didn't see was how to stop the infinite loop if the Collatz Conjecture does NOT reach the value of 1! In the generic sense, this would be the error-catching phase of the development of the code.
yep fair point carla. i don't tend to put in error catching when building a prototype unless i am struggling with the prototype itself. when it comes time to rework/rebuild/productionise it then yes, error trapping is crucial.
as it regards to this particular problem - do you have something in mind for stopping the infinite loop?
October 3, 2011 at 8:35 am
It was similar to your approach.
I started with the math first, next came the decision of how I wanted the output structured - that is was it going to return the individual steps or just a Bit with some details. I chose the latter cuz it hardly matters how many steps it takes or what the steps look like. This assertion merely insists that all number will dwindle down to 1.
By the way, I was reading about Collatz not long ago and I think a solution (an actual proof that all numbers share this property) is probably reached through math induction. The code we attempted to write is really a way to solve this brute force. We could, in theory, exhaustively run positive integers through our code and "see" that they all behave the same way but that is hardly proving it. What I think might be the way to prove it would involve something like this... 1. Let's say there is a number N for which we assume that Collatz is true, 2. Now, assume that for N + 1 Collatz isn't true, 3. find a way to prove that statement 2 is false. If we can do that, then, we would have proven it for all positive numbers.
Of course, at the moment I only think it's a way to attempt to solve. I lack the math skills to go about it in any proper scientific way. Guess I'll leave it to the math world....
October 3, 2011 at 8:41 am
I'd like to see the solution 'learning' about numbers that it knows will eventually reach 1 and therefore cutting corners
great idea, jamie. well worth having a go.
October 3, 2011 at 9:25 am
The math is pathetically simple and failing to see patterns is the mark of a beginning programmer. Some problems are too difficult to see patterns in until one has experience with them. This is the evolutionary process.
If number is odd do
n x 3 + 1
which basically converts any odd number to an even one since "odd times itself an even number of times yields an even result" and "odd times itself an odd number of times yields an odd result"
If number is even
n / 2
which eventually reduces all even numbers to 1.
As Tesla said of Edison something like: a little hypothesis and he could have saved him 90% of his effort in finding a filament for the light bulb.
October 3, 2011 at 9:37 am
Bill,
If number is even
n / 2
which eventually reduces all even numbers to 1.
Not so fast - it only reduces 2n quickly to 1. Some even numbers (18, say) bounce around for quite a while which is the point of the whole problem.
Jamie.
October 3, 2011 at 10:04 am
The math is pathetically simple and failing to see patterns is the mark of a beginning programmer.
The Collatz conjuecture is deceptively difficult, that's why it remains unsolved.
Yes, 3n+1 converts an odd number into an even number that is larger than itself.
If number is even
n / 2
which eventually reduces all even numbers to 1.
No, it reduces powers of 2 to 1. It reduces other even numbers to some odd number. An early long sequence is for 9
9 - 28 - 14 - 7 - 22 - 11 - 34 - 17 - 52 - 26 - 13 - 40 - 20 - 10 - 5 - 16 - 8 - 4 - 2 - 1
The converse of the conjecture would say:
There is some odd number x, such that the iteration returns to x (or goes to infinity).
This means, for the original problem:
1. You only need to check odd numbers
2. The stopping point for a disproof is that the current number equals the starting number.
3. Every number touched along the way is solved with the original number.
--
JimFive
Viewing 15 posts - 1 through 15 (of 18 total)
You must be logged in to reply to this topic. Login to reply