• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EST 13:45
CET 19:45
KST 03:45
  • 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
[ASL22] Finals Preview: Sweet Victory!12[ASL22] Ro4 Preview: Mirror Mirror6[ASL22] Ro8 Preview: Within Reach5[ASL22] Ro8 Preview: In A Tizzy11[ASL22] Ro16 Preview: Holy Diver5
Community News
Weekly Cups (Oct 26 - Nov 1): MaxPax, herO, Solar win0Weekly Cups (October 19-25): Clem triples first in 5.0.175Evil Geniuses - shutting down23ISSL (IntoTheTV x SOOP SC2 League): Premier7Weekly Cups (October 12-18): 5.0.17 era begins1
StarCraft 2
General
Serral's getting trashed by New Catsle's Mind No more SC2 streamers on team liquid? StarCraft open world shooter announced at BlizzCon [D] Hacker peak in sc2 ? Liquibets sc2 season 30
Tourneys
SC2 iNu's Battles #22 SC4ALL: II Venue Change Announcement! Sparkling Tuna Cup - Weekly Open Tournament WardiTV Mondays ISSL (IntoTheTV x SOOP SC2 League): Premier
Strategy
[H] ZvP Mid-Late Game: Stalkers Collossi HT
Custom Maps
Starcraft 2 Advance [G] How to playtest arcade maps [D] the control group Simple Questions/Answers
External Content
The PondCast: SC2 News & Results Mutation # 551 Robotic Revival Mutation # 550 Graveyard Shift Mutation # 549 Endless Sparkles
Brood War
General
List of top players active on ShieldBattery Rollback Netcode in Brood War [Megathread] Daily Funny Videos BW General Discussion Cwal.gg not working
Tourneys
[$1250] International ShieldBattery League [Megathread] Daily Proleagues Small VOD Thread 2.0 KCM Race Survival 2026 Season 4
Strategy
50,000-Word Terran Builds Memo 2026-10-22 Cliff Jump Revisited (1 in a 1000 strategy) Simple Questions, Simple Answers
Other Games
General Games
Nintendo Switch Thread General RTS Discussion Thread ZeroSpace Early Access is Now Live! Path of Exile Stormgate/Frost Giant Megathread
Dota 2
Dota 2 Champions League Season 3 Begins April 25!
League of Legends
[TL LoL EUW IHs] Teemo shall perish
Heroes of the Storm
Heroes of the Storm 2.0
Hearthstone
Deck construction bug
TL Mafia
TL Mafia Community Thread
Community
General
Trading/Investing Thread US Politics Mega-thread Russo-Ukrainian War Thread Dating: How's your luck? Things Aren’t Peaceful in Palestine
Fan Clubs
Fan Club Resource Thread Reynor Fan Club The Flash Fan Club
Media & Entertainment
Movie Discussion! Anime Discussion Thread [Manga] One Piece
Sports
Football (Soccer) Thread TeamLiquid Health and Fitness Initiative For 2023 MLB/Baseball 2023
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread
TL Community
The Automated Ban List Recent Gifted Posts
Blogs
The time I organised my…
AssyrianKing
Playlenda
Playlendapro
Why I built Repalyzer (1.1.…
BlueStar
Innovate or Game Over?
TrAiDoS
ShieldBattery on Mac
Kraekkling
[ASL22] Ro4 Day1 Ticket Giv…
bITt.mAN
Can Bots Beat Pros?? Starcr…
namkraft
Customize Sidebar...

Website Feedback

Closed Threads



Active: 14347 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
Canada3502 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
Netherlands2763 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
Monday Night Weeklies
02:00
#69
TaKeTV 327
TKL 319
SteadfastSC256
ZombieGrub14
LiquipediaDiscussion
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
ByuN 516
TKL 319
SteadfastSC 256
ZombieGrub14
EmSc Tv 0
StarCraft: Brood War
Shuttle 387
Stork 91
firebathero 90
ProTech68
sSak 48
Barracks 32
910 16
soO 15
Counter-Strike
pashabiceps2322
byalli534
x6flipin250
jkaem164
gobbtv139
Heroes of the Storm
Grubby2307
Other Games
tarik_tv5329
FrodaN1080
Liquid`RaSZi961
Liquid`Hasu232
ArmadaUGS126
QueenE105
Trikslyr66
NeuroSwarm45
UpATreeSC40
Railgan33
Chillindude16
Organizations
Counter-Strike
PGL72
StarCraft 2
EmSc Tv 0
EmSc2Tv 0
[ Show 14 non-featured ]
StarCraft 2
• Reevou 4
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• Migwel
StarCraft: Brood War
• blackmanpl 34
• Pr0nogo 1
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
League of Legends
• Nemesis2378
Other Games
• imaqtpie793
• Shiphtur626
Upcoming Events
Replay Cast
4h 15m
Sparkling Tuna Cup
15h 15m
WardiTV Invitational
17h 15m
YoungYakov vs Lambo
SHIN vs TBD
Percival vs Shameless
Solar vs TBD
OSC
1d 4h
ByuN vs MaxPax
herO vs Krystianer
Percival vs Shameless
LetaleX vs YoungYakov
Nicoract vs Gerald
GgMaChine vs ArT
PiGosaur Cup
1d 6h
INu's Battles
1d 17h
ByuN vs Classic
3D!Clan Event
1d 21h
The PondCast
2 days
KCM Race Survival
2 days
WardiTV Invitational
2 days
[ Show More ]
Ultimate Battle
3 days
CranKy Ducklings
4 days
IPSL
4 days
TerrOr vs IJ_Terran
rasowy vs Hazorath
Sparkling Tuna Cup
5 days
IPSL
5 days
Art_Of_Turtle vs KameZerg
Radley vs George
Replay Cast
6 days
WardiTV Weekly
6 days
Liquipedia Results

Completed

Proleague 2026-11-06
Blizzard Classic Cup 2026
HCC Season 3

Ongoing

Acropolis #5
KCM Race Survival 2026 Season 4
International ShieldBattery League
Individual League
BSL Season 23
IPSL Winter 2026-27
Calamity Cup Div. A Season 8
IEM Beijing 2026
PGL Masters Bucharest 2026
Stake Ranked Episode 5
1win Private Club #2
Thunderpick World Champ. '26
ESL Pro League Season 24
Stake Ranked Episode 4
1win Private Club #1
Logitech G Play Connect 2026
SL StarSeries Fall 2026
FISSURE Playground #3
BLAST Open Fall 2026

Upcoming

YSL S4
Sector 951
SC4ALL II: Brood War
BSL 23: Non-Korean Championship
HSC XXX
Stellar Fest 2: Lunar Cup
StarCraft2 Weekly Open Tournament 2026 Grand Finals
SC4ALL II: StarCraft II
Kung Fu Cup 2026 Grand Finals
RSL Offline Finals
Underdog Cup 2026 Div 2-3
PGL Bucharest 2027
BLAST Bounty Winter 2027
eXTREMESLAND 2026
PGL Major Singapore 2026
Stake Ranked Episode 6
BLAST Rivals Fall 2026
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 © 2026 TLnet. All Rights Reserved.