Jump to content

Sky Slate Blueberry Blackcurrant Watermelon Strawberry Orange Banana Apple Emerald Chocolate
Photo

Longest Collatz sequence


  • Please log in to reply
10 replies to this topic
smorgasboard
  • Members
  • 660 posts
  • Last active: Jan 14 2016 08:53 AM
  • Joined: 18 Jul 2012

Found an interesting way to learn coding, that is by solving problems at

http://projecteuler.net/

 

Solved till 13 by getting help from #ahk IRC and made a repertoire of the same happy.png will surely help in the long run.

 

Reached

http://projecteuler.net/problem=14

 

made the code for the same, i.e.

#NoEnv  ; Recommended for performance and compatibility with future AutoHotkey releases.
; #Warn  ; Enable warnings to assist with detecting common errors.
SendMode Input  ; Recommended for new scripts due to its superior speed and reliability.
SetWorkingDir %A_ScriptDir%  ; Ensures a consistent starting directory.
compare := 0
count := 0
number := 2
Loop, 1000000
{
K := number
						Loop,
						{
									if ( K = 1 )
									{
										count := Count + 1
									sofar .= ans k "        " count "`n"
									;MsgBox, %sofar% 
									compare := compare > count ? compare : count
									MsgBox, %sofar%And the highest so far as per the requirement of the problem is %compare%
									Clipboard := compare
									TrayTip, %number%, %compare%
									
									count := 0
									break
									}
											Loop
											{
														if ( K = 1 )
														{
														;MsgBox reached %ans% finally
														break
														}	
											rem := mod(k, 2) 
											;MsgBox	%k% leaves a remainder  %rem%	
	
														if ( rem = 0 )
														{
														ans .= k "->"
														n := k//2
														;MsgBox %k% results in %n%
														K := N
														count := count + 1
														}
														else
														{
														ans .= k "->"
														n := 3*k + 1
														;MsgBox %k% results %n%
														K := N
														count := count + 1
														}
											}
							}
ans :=
number := number + 1
}






that runs fine but i think to loop  for 1000000 times will be something not elegant. so i think if the code could assign every number it's  value like 

 

eg. for 2 it is 2 ->1     2    ====> here if i could assign

 

2 for the number 2 &

1 for the number 1

 

for 3 it is 3->10->5->16->8->4->2->1     8     ====> here if i could assign

 

8 for the number 3,

7 for the number 10, ***

6 for the number 5,

5 for the number 16,

4 for the number 8,

3 for the number 4, **

2 for the number 2,

2 for the number 1,

 

So basically if the script could check for a number whether it's value is already cached somewhere then use that value and in case it's value is not assigned then generate it's value as per the current script. For example for 4, as the value of 4 has already been assigned ** 3 then use this value and move to 5, 5 also done which has the value 6, so move to 7, since 7 is not done it generates the value for 7 like 7->22->11->34->17->52->26->13->40->20->10 ( already generated so no need to move further just add 10 from ( 7->22->11->34->17->52->26->13->40->20 ) and add 7 from *** to get 17. so on forth.

 

 

In this manner there script can run through 1000000 times without hogging much resources. How to do that if possible? Thanks as usual in advance

 

 

 



VxE
  • Moderators
  • 3622 posts
  • Last active: Dec 24 2015 02:21 AM
  • Joined: 07 Oct 2006
Spoiler

The number under 1 million that gives the longest sequence is 837799.

smorgasboard
  • Members
  • 660 posts
  • Last active: Jan 14 2016 08:53 AM
  • Joined: 18 Jul 2012

@VXE

Jaw Dropping code always from you.  Wish i could decipher your code!

if i am able to discern it i  shall add comments for your approval.

:) thanks..



MasterFocus
  • Moderators
  • 4323 posts
  • Last active: Jan 28 2016 01:38 AM
  • Joined: 08 Apr 2009

As always VxE, clever ternary (using & and >>).

Related: http://rosettacode.o...ence#AutoHotkey

( I would link this thread but I have just discovered that over 30 pages from that topic are now missing! shocked.png sad.png )


-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Antonio França -- git.io -- github.com -- ahk4.net -- sites.google.com -- ahkscript.org

Member of the AHK community since 08/Apr/2009. Moderator since mid-2012.


VxE
  • Moderators
  • 3622 posts
  • Last active: Dec 24 2015 02:21 AM
  • Joined: 07 Oct 2006
If you prefer, you can swap (x&1) with Mod(X,2) and (x>>1) with (x//2). The speed won't change significantly.

@smorgasboard: the crux of my code is the memoization scheme. Since each sequence is being calculated in order, when a sequence's N value goes below its starting value, we know the rest of that sequence has already been calculated. So the code simply appends the previously calculated sequence, adds its length, and moves on to the next number.

strobo
  • Members
  • 359 posts
  • Last active: Mar 10 2015 08:13 PM
  • Joined: 19 Jun 2012

@VxE
    Nice code and effective memoization scheme. Though, for this task the
    whole .sequence property is superfluous, i.e. an array
    sequ_starting_element_To_sequ_length would support all the relevant information
    and costs much less memory. To print the longest sequence at the
    end just calculate the desired sequence again.


Regards,
Babba

smorgasboard
  • Members
  • 660 posts
  • Last active: Jan 14 2016 08:53 AM
  • Joined: 18 Jul 2012

@VxE i commented the lines that i could not understand.

#NoEnv  ; Recommended for performance and compatibility with future AutoHotkey releases.
; #Warn  ; Enable warnings to assist with detecting common errors.
SendMode Input  ; Recommended for new scripts due to its superior speed and reliability.
SetWorkingDir %A_ScriptDir%  ; Ensures a consistent starting directory.
/*
	Collatz sequences

	N -> N/2 (if N is even)
	N -> 3N + 1 (if N is odd)
*/

#NoEnv
SetBatchLines, -1
time := A_now
trials := 1000000 ; change this
maxlen := 0 ; but not this
results := [{sequence:"1",length:1}] ; what does this line do?
Loop % trials - 1
{
	N := K := A_Index + 1
	L := 1
	results[K] := {} ; and this ?
	results[K].sequence := N ; and this?
	While K < N := Mod(N, 2) ? 3 * N + 1 : N // 2 ; it seems as if it runs the following line with the condition that While K is less than N where N is equal to 3n+1 OR n/2 depending upon n being odd or even respectively, right?
		L++, results[K].sequence .= "," N ; results[K].sequence ; same from above cannot discern.
	results[K].sequence .= "," results[N].sequence ; same as line 17..
	results[K].length := L + results[N].length ; almost same...
	if ( maxlen < results[K].length ) ; it seems as if %results[K].length% is some number?
	{
		maxlen := results[K].length
		longest := results[K].sequence
	}
	if !mod( A_Index, 3577 ) ; why specifically 3577?
		tooltip % Round( A_Index * 100.0 / trials, 2 ) "%"
}
tooltip
elapsed := A_now - time
msgbox %longest% in %elapsed%

mm...unable to understand the "[]" and "." stuff at all. Also googled memoization and it seems exactly what i asked. thanks again..



just me
  • Members
  • 1496 posts
  • Last active: Nov 03 2015 04:32 PM
  • Joined: 28 May 2011

What about this, is it a bit more clear?

 

Spoiler

Prefer ahkscript.org for the time being.


MasterFocus
  • Moderators
  • 4323 posts
  • Last active: Jan 28 2016 01:38 AM
  • Joined: 08 Apr 2009

If you don't need the sequence, it's a bit faster:

(I have AHK 1.0 installed here, so I didn't use real arrays)

#NoEnv
SetBatchLines, -1
trials := 1000000 ; change this
maxlen := 0 ; but not this
L1 := 1
Loop % trials - 1
{
    N := K := A_Index + ( L := 1 )
    While ( K < N := N & 1 ? 3 * N + 1 : N >> 1 )
        L++
    L%K% := L + L%N%
    if ( maxlen < L%K% )
        maxlen := L%K%, longest := K
    if !mod( A_Index, 7000 )
        tooltip % Round( A_Index * 100.0 / trials, 2 ) "%"
}
tooltip
;listvars
msgbox % "Longest is " longest " with a " maxlen "-long sequence."

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Antonio França -- git.io -- github.com -- ahk4.net -- sites.google.com -- ahkscript.org

Member of the AHK community since 08/Apr/2009. Moderator since mid-2012.


guest3456
  • Members
  • 1704 posts
  • Last active: Nov 19 2015 11:58 AM
  • Joined: 10 Mar 2011
longest tab spacing ever?

GeekDude
  • Spam Officer
  • 391 posts
  • Last active: Oct 05 2015 08:13 PM
  • Joined: 23 Nov 2009

VxE: Your code is amazing! I'm not sure why I didn't write mine like that. Yours executes in around 6 seconds (with fluff stripped out), while mine does it in 10.

 

Edit: Excuse the lack of indentation, it seems the forum strips out tab characters.

Prob14()
{
Collatz := []
Loop, 999999
{
n := A_Index, Chain := 1
While (n != 1)
{
if Mod(n,2)
{
if (Collatz[n])
{
Chain += Collatz[n]
break
}
n := 3*n+1
}
else
n /= 2
Chain++
}
if (Mod(A_Index, 2))
Collatz[A_Index] := Chain
if (Chain > Largest)
Largest := Chain, Answer := A_Index
}
return Answer
}