• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 10:48
CEST 16:48
KST 23:48
  • Home
  • Forum
  • Calendar
  • Streams
  • Liquipedia
  • Features
  • Store
  • EPT
  • TL+
  • StarCraft 2
  • Brood War
  • Smash
  • Heroes
  • Counter-Strike
  • Overwatch
  • Liquibet
  • Fantasy StarCraft
  • TLPD
  • StarCraft 2
  • Brood War
  • Blogs
Forum Sidebar
Events/Features
News
Featured News
RSL Season 1 - Final Week6[ASL19] Finals Recap: Standing Tall12HomeStory Cup 27 - Info & Preview18Classic wins Code S Season 2 (2025)16Code S RO4 & Finals Preview: herO, Rogue, Classic, GuMiho0
Community News
Firefly given lifetime ban by ESIC following match-fixing investigation17$25,000 Streamerzone StarCraft Pro Series announced7Weekly Cups (June 30 - July 6): Classic Doubles7[BSL20] Non-Korean Championship 4x BSL + 4x China10Flash Announces Hiatus From ASL82
StarCraft 2
General
The GOAT ranking of GOAT rankings RSL Revival patreon money discussion thread Weekly Cups (June 30 - July 6): Classic Doubles Server Blocker RSL Season 1 - Final Week
Tourneys
RSL: Revival, a new crowdfunded tournament series Sparkling Tuna Cup - Weekly Open Tournament FEL Cracov 2025 (July 27) - $8000 live event $5,100+ SEL Season 2 Championship (SC: Evo) $25,000 Streamerzone StarCraft Pro Series announced
Strategy
How did i lose this ZvP, whats the proper response Simple Questions Simple Answers
Custom Maps
External Content
Mutation # 481 Fear and Lava Mutation # 480 Moths to the Flame Mutation # 479 Worn Out Welcome Mutation # 478 Instant Karma
Brood War
General
Flash Announces Hiatus From ASL [ASL19] Finals Recap: Standing Tall BGH Auto Balance -> http://bghmmr.eu/ BW General Discussion A cwal.gg Extension - Easily keep track of anyone
Tourneys
[Megathread] Daily Proleagues 2025 ACS Season 2 Qualifier Small VOD Thread 2.0 Last Minute Live-Report Thread Resource!
Strategy
Simple Questions, Simple Answers I am doing this better than progamers do.
Other Games
General Games
Stormgate/Frost Giant Megathread Path of Exile CCLP - Command & Conquer League Project The PlayStation 5 Nintendo Switch Thread
Dota 2
Official 'what is Dota anymore' discussion
League of Legends
Heroes of the Storm
Simple Questions, Simple Answers Heroes of the Storm 2.0
Hearthstone
Heroes of StarCraft mini-set
TL Mafia
TL Mafia Community Thread Vanilla Mini Mafia
Community
General
Russo-Ukrainian War Thread US Politics Mega-thread Things Aren’t Peaceful in Palestine The Accidental Video Game Porn Archive Stop Killing Games - European Citizens Initiative
Fan Clubs
SKT1 Classic Fan Club! Maru Fan Club
Media & Entertainment
Movie Discussion! [Manga] One Piece Anime Discussion Thread [\m/] Heavy Metal Thread
Sports
2024 - 2025 Football Thread Formula 1 Discussion NBA General Discussion TeamLiquid Health and Fitness Initiative For 2023 NHL Playoffs 2024
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread
TL Community
The Automated Ban List
Blogs
Men Take Risks, Women Win Ga…
TrAiDoS
momentary artworks from des…
tankgirl
from making sc maps to makin…
Husyelt
StarCraft improvement
iopq
Trip to the Zoo
micronesia
Customize Sidebar...

Website Feedback

Closed Threads



Active: 738 users

Project Euler, Problem 14.

Blogs > Adeny
Post a Reply
1 2 Next All
Adeny
Profile Blog Joined January 2009
Norway1233 Posts
November 04 2009 19:12 GMT
#1
Yo, so I started project euler a couple days ago, and some of the problems are pretty challenging already, for someone who's only had 10 grades of math. I've done quite a bit of googling, compared some codes and whatnot, but i never found a c++ example, and it's the only language i'm somewhat familiar with, so other's solutions are hard to understand. I know that asking for help on a project euler problem is pretty lame, but i'm completely stuck and very curious as to what i'm doing wrong. Not really the right place to ask either, but I don't know where else would be more appropriate, so here we go:

The problem:
+ Show Spoiler +

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.


I've checked and double-checked my solution many times but I can't for the life of me see how it's wrong, here's the code: (Pretty sloppy but w/e, it's short)

+ Show Spoiler +

#include <iostream>
#include <windows.h>
#include "conio.h"

using namespace std;

int temp = 0; // temp stores chain length
int maxnum = 0; // max chain
int begnum = 0; // max beginning number
int tempbegnum = 0; // temp max beginning number
void sequence(int n)
{
temp = 0;
tempbegnum = n;
while (n > 1)
{
if (n % 2 == 0)
{
n = n/2;
}
else
{
n = n*3+1;
}
temp++;
}
if (temp > maxnum && n == 1)
{
maxnum = temp;
begnum = tempbegnum;
}

return;
}


int main()
{

for (int i = 0; i < 1000000; i++)
{
sequence(i);
}
cout << maxnum << endl << begnum;

_getch();
return 0;
}


*
Kau *
Profile Joined March 2007
Canada3500 Posts
November 04 2009 19:23 GMT
#2
I just skimmed your code so this question might be useless, but what happens if several chains have the same chain length? Do you take the smallest number or the largest?
Moderator
Adeny
Profile Blog Joined January 2009
Norway1233 Posts
November 04 2009 19:24 GMT
#3
I didn't really think of it because I assumed one definite answer, but only if the current chain is OVER the max chain will it be stored.
CTStalker
Profile Blog Joined November 2004
Canada9720 Posts
November 04 2009 19:30 GMT
#4
don't have the time now to help out, but a general tip: if you want people to read your code, some indenting will help.
By the way, my name is Funk. I am not of your world
Adeny
Profile Blog Joined January 2009
Norway1233 Posts
November 04 2009 19:31 GMT
#5
I'm sorry that would be the forum's fault. Don't know how to fix it.
CTStalker
Profile Blog Joined November 2004
Canada9720 Posts
November 04 2009 19:32 GMT
#6
oh. right.

my bad
By the way, my name is Funk. I am not of your world
CTStalker
Profile Blog Joined November 2004
Canada9720 Posts
November 04 2009 19:40 GMT
#7

#include <iostream>
#include <windows.h>
#include "conio.h"

using namespace std;

int temp = 0; // temp stores chain length
int maxnum = 0; // max chain
int begnum = 0; // max beginning number
int tempbegnum = 0; // temp max beginning number
void sequence(int n)
{
temp = 0;
tempbegnum = n;
while (n > 1)
{
if (n % 2 == 0)
{
n = n/2;
}
else
{
n = n*3+1;
}
temp++;
}

if (temp > maxnum && n == 1)
{
maxnum = temp;
begnum = tempbegnum;
}

return;
}


int main()
{

for (int i = 0; i < 1000000; i++)
{
sequence(i);
}
cout << maxnum << endl << begnum;

_getch();
return 0;
}
By the way, my name is Funk. I am not of your world
Adeny
Profile Blog Joined January 2009
Norway1233 Posts
November 04 2009 19:42 GMT
#8
Sick, how'd you do that? For future reference.
Insane
Profile Blog Joined November 2003
United States4991 Posts
Last Edited: 2009-11-04 20:01:47
November 04 2009 19:52 GMT
#9
With the [code] tag
You could hit quote and it shows you what he used to make his post.


Without actually writing code or solving the problem: are you sure you are not overflowing int?
category
Profile Joined July 2009
United States85 Posts
November 04 2009 19:53 GMT
#10
Project Euler is badass. Good for you for taking on the challenge. You will learn a lot in the process.
Navane
Profile Blog Joined February 2007
Netherlands2748 Posts
November 04 2009 20:00 GMT
#11
it counts one to many. But since it does it with al of the numbers, the number with the most is still the number with the most. But the array is one number shorter.

(i tested it with i < 5, it says 7 / 3, meaning array(3) has seven items, which is untrue: 3 10 5 16 8 4 2 1)
Insane
Profile Blog Joined November 2003
United States4991 Posts
Last Edited: 2009-11-04 20:12:06
November 04 2009 20:09 GMT
#12
OK, I did it in C# using a similar method to yours and it works fine using a long instead of an int. (I don't mean for the chain length--I mean for the value that you actually change to n/2 or 3n+1)

On November 05 2009 05:00 Navane wrote:
it counts one to many. But since it does it with al of the numbers, the number with the most is still the number with the most. But the array is one number shorter.

(i tested it with i < 5, it says 7 / 3, meaning array(3) has seven items, which is untrue: 3 10 5 16 8 4 2 1)

I don't really understand what you're trying to communicate with this post. He never uses an array...?


e: In case it's not clear, I never ran your code
This was my C# solution. And no I don't write actual ugly code like the for statement in production :D

+ Show Spoiler +
        static void Main(string[] args)
{
int longest = 0;
int longestIndex = 1;
for (int i = 1; i < 1000000; i++)
{
int temp = ChainLength(i);
if (temp > longest)
{
longestIndex = i;
longest = temp;
}
}
Console.WriteLine(string.Format("{0}: {1}", longestIndex, longest));
Console.Read();
}

private static int ChainLength(long a)
{
int c;
for (c = 0; a != 1; c++, a = (a % 2 == 0) ? a / 2 : (3 * a) + 1) ;
return c;
}
Adeny
Profile Blog Joined January 2009
Norway1233 Posts
Last Edited: 2009-11-04 20:12:49
November 04 2009 20:11 GMT
#13
OK, I did it in C# using a similar method to yours and it works fine using a long instead of an int. (I don't mean for the chain length--I mean for the value that you actually change to n/2 or 3n+1)


I don't even know what to say to this... I'm so bad.
Atleast I got it solved, right? ONWARDS!
Insane
Profile Blog Joined November 2003
United States4991 Posts
Last Edited: 2009-11-04 20:13:28
November 04 2009 20:13 GMT
#14
On November 05 2009 05:11 Adeny wrote:
Show nested quote +
OK, I did it in C# using a similar method to yours and it works fine using a long instead of an int. (I don't mean for the chain length--I mean for the value that you actually change to n/2 or 3n+1)


I don't even know what to say to this... I'm so bad.

You mean you don't know what to say that you missed that, or you don't know what I mean?
e: nevermind, you edited your post so it's clear what you mean
Thratur
Profile Blog Joined June 2008
Canada917 Posts
November 04 2009 20:36 GMT
#15
How do you know it's wrong?
AssuredVacancy
Profile Blog Joined September 2008
United States1167 Posts
November 04 2009 20:36 GMT
#16
I'm thinking a way to optimize it would be have an array to store the results of lower numbers of how long before the chain terminates. AKA, if you did sequence(13), and found that it takes 10 steps before it ends, you store 10 at array index 13, so the NEXT time a bigger number arrives at 13, you know that it's gonna end in 10 steps so you don't have to waste time calculating the rest. Do it recursively and it should be wayyyy faster.
We spend our youth attaining wealth, and our wealth attaining youth.
searcher
Profile Blog Joined May 2009
277 Posts
November 04 2009 20:36 GMT
#17
If you want to learn even more about this:
Collatz Conjecture
Adeny
Profile Blog Joined January 2009
Norway1233 Posts
November 04 2009 20:53 GMT
#18
On November 05 2009 05:36 AssuredVacancy wrote:
I'm thinking a way to optimize it would be have an array to store the results of lower numbers of how long before the chain terminates. AKA, if you did sequence(13), and found that it takes 10 steps before it ends, you store 10 at array index 13, so the NEXT time a bigger number arrives at 13, you know that it's gonna end in 10 steps so you don't have to waste time calculating the rest. Do it recursively and it should be wayyyy faster.


Interesting, but execution time is near-immediate on this, and I'm not good enough to think about optimalizations yet, it's challenging enough just to come up with the right answer, as you've seen.
Also I noticed now that when my program didn't work with the beginning value set to zero i changed the if (tempstring > maxstring) or whatever to if (tempstring > maxstring && n == 1), which is obviously very stupid as that gets checked every loop, right after while (n > 1), completely unecessary. I don't know where my mind whas at when I decided upon that instead of just changing it to start counting from 3 or something.
iSiN
Profile Blog Joined March 2009
United States1075 Posts
November 04 2009 20:54 GMT
#19
you program with C# peter...this makes me sad
Grouty @HoN/PCKJ <--<333 || Jaedong Fan Cafe GFX
Insane
Profile Blog Joined November 2003
United States4991 Posts
Last Edited: 2009-11-04 22:30:22
November 04 2009 22:30 GMT
#20
On November 05 2009 05:54 iSiN wrote:
you program with C# peter...this makes me sad

Programming in C# is part of my job. What's wrong with that?
1 2 Next All
Please log in or register to reply.
Live Events Refresh
Next event in 13m
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
Hui .238
Vindicta 125
StarCraft: Brood War
EffOrt 1645
firebathero 970
Larva 800
Mini 363
BeSt 315
Nal_rA 211
Leta 199
Barracks 97
Dewaltoss 73
ToSsGirL 70
[ Show more ]
Sharp 69
GoRush 61
Shinee 48
Movie 48
Aegong 34
yabsab 21
Hm[arnc] 19
Terrorterran 16
IntoTheRainbow 10
SilentControl 7
Dota 2
Gorgc8363
qojqva2546
League of Legends
Dendi844
Heroes of the Storm
Khaldor686
Liquid`Hasu360
Other Games
tarik_tv41886
gofns22783
FrodaN7191
singsing2289
B2W.Neo2035
DeMusliM714
shahzam534
KnowMe291
XaKoH 193
Rex15
ToD12
Organizations
StarCraft: Brood War
Kim Chul Min (afreeca) 6
StarCraft 2
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 16 non-featured ]
StarCraft 2
• StrangeGG 80
• HeavenSC 19
• Adnapsc2 13
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• LaughNgamezSOOP
• Migwel
• sooper7s
StarCraft: Brood War
• Michael_bg 8
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
Dota 2
• Ler117
League of Legends
• Nemesis5062
Upcoming Events
FEL
13m
Elazer vs Spirit
Gerald vs MaNa
CranKy Ducklings5
BSL20 Non-Korean Champi…
3h 13m
Bonyth vs Dewalt
QiaoGege vs Dewalt
Hawk vs Bonyth
Sziky vs Fengzi
Mihu vs Zhanhun
QiaoGege vs Zhanhun
Fengzi vs Mihu
Wardi Open
20h 13m
Replay Cast
1d 19h
WardiTV European League
2 days
PiGosaur Monday
2 days
uThermal 2v2 Circuit
3 days
Replay Cast
3 days
The PondCast
3 days
Replay Cast
4 days
[ Show More ]
Epic.LAN
4 days
CranKy Ducklings
5 days
Epic.LAN
5 days
BSL20 Non-Korean Champi…
6 days
Bonyth vs Sziky
Dewalt vs Hawk
Hawk vs QiaoGege
Sziky vs Dewalt
Mihu vs Bonyth
Zhanhun vs QiaoGege
QiaoGege vs Fengzi
Sparkling Tuna Cup
6 days
Liquipedia Results

Completed

KCM Race Survival 2025 Season 2
HSC XXVII
NC Random Cup

Ongoing

JPL Season 2
BSL 2v2 Season 3
Acropolis #3
CSL 17: 2025 SUMMER
Copa Latinoamericana 4
Jiahua Invitational
2025 ACS Season 2: Qualifier
BSL20 Non-Korean Championship
CSLPRO Last Chance 2025
Championship of Russia 2025
Murky Cup #2
BLAST.tv Austin Major 2025
ESL Impact League Season 7
IEM Dallas 2025
PGL Astana 2025
Asian Champions League '25
BLAST Rivals Spring 2025
MESA Nomadic Masters

Upcoming

CSL Xiamen Invitational
CSL Xiamen Invitational: ShowMatche
2025 ACS Season 2
CSLPRO Chat StarLAN 3
BSL Season 21
K-Championship
RSL Revival: Season 2
uThermal 2v2 Main Event
SEL Season 2 Championship
FEL Cracov 2025
Esports World Cup 2025
Underdog Cup #2
StarSeries Fall 2025
FISSURE Playground #2
BLAST Open Fall 2025
BLAST Open Fall Qual
Esports World Cup 2025
BLAST Bounty Fall 2025
BLAST Bounty Fall Qual
IEM Cologne 2025
FISSURE Playground #1
TLPD

1. ByuN
2. TY
3. Dark
4. Solar
5. Stats
6. Nerchio
7. sOs
8. soO
9. INnoVation
10. Elazer
1. Rain
2. Flash
3. EffOrt
4. Last
5. Bisu
6. Soulkey
7. Mini
8. Sharp
Sidebar Settings...

Advertising | Privacy Policy | Terms Of Use | Contact Us

Original banner artwork: Jim Warren
The contents of this webpage are copyright © 2025 TLnet. All Rights Reserved.