• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 14:07
CEST 20:07
KST 03:07
  • 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
[ASL19] Finals Recap: Standing Tall9HomeStory Cup 27 - Info & Preview18Classic wins Code S Season 2 (2025)16Code S RO4 & Finals Preview: herO, Rogue, Classic, GuMiho0TL Team Map Contest #5: Presented by Monster Energy6
Community News
Flash Announces Hiatus From ASL50Weekly Cups (June 23-29): Reynor in world title form?12FEL Cracov 2025 (July 27) - $8000 live event16Esports World Cup 2025 - Final Player Roster16Weekly Cups (June 16-22): Clem strikes back1
StarCraft 2
General
The SCII GOAT: A statistical Evaluation The GOAT ranking of GOAT rankings How does the number of casters affect your enjoyment of esports? Statistics for vetoed/disliked maps Esports World Cup 2025 - Final Player Roster
Tourneys
Master Swan Open (Global Bronze-Master 2) RSL: Revival, a new crowdfunded tournament series [GSL 2025] Code S: Season 2 - Semi Finals & Finals $5,100+ SEL Season 2 Championship (SC: Evo) FEL Cracov 2025 (July 27) - $8000 live event
Strategy
How did i lose this ZvP, whats the proper response Simple Questions Simple Answers
Custom Maps
[UMS] Zillion Zerglings
External Content
Mutation # 480 Moths to the Flame Mutation # 479 Worn Out Welcome Mutation # 478 Instant Karma Mutation # 477 Slow and Steady
Brood War
General
BGH Auto Balance -> http://bghmmr.eu/ Player “Jedi” cheat on CSL Unit and Spell Similarities Help: rep cant save Flash Announces Hiatus From ASL
Tourneys
[Megathread] Daily Proleagues [BSL20] Grand Finals - Sunday 20:00 CET Small VOD Thread 2.0 [BSL20] GosuLeague RO16 - Tue & Wed 20:00+CET
Strategy
Simple Questions, Simple Answers I am doing this better than progamers do.
Other Games
General Games
Stormgate/Frost Giant Megathread Nintendo Switch Thread Path of Exile What do you want from future RTS games? Beyond All Reason
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
US Politics Mega-thread Things Aren’t Peaceful in Palestine Russo-Ukrainian War Thread Trading/Investing Thread The Games Industry And ATVI
Fan Clubs
SKT1 Classic Fan Club! Maru Fan Club
Media & Entertainment
Anime Discussion Thread [Manga] One Piece [\m/] Heavy Metal Thread
Sports
Formula 1 Discussion 2024 - 2025 Football Thread 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
Blogs
Culture Clash in Video Games…
TrAiDoS
from making sc maps to makin…
Husyelt
Blog #2
tankgirl
StarCraft improvement
iopq
Trip to the Zoo
micronesia
Customize Sidebar...

Website Feedback

Closed Threads



Active: 752 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
Big Brain Bouts
16:00
#97
RotterdaM680
Liquipedia
FEL
16:00
Polish Championship: Qualifier
IndyStarCraft 219
CranKy Ducklings71
Liquipedia
WardiTV European League
16:00
Swiss Groups Day 2
Jumy vs ArTLIVE!
YoungYakov vs Shameless
uThermal vs Fjant
Nicoract vs goblin
Harstem vs Gerald
WardiTV838
TKL 239
Liquipedia
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
RotterdaM 680
TKL 239
IndyStarCraft 219
Hui .193
UpATreeSC 70
StarCraft: Brood War
Britney 30653
Calm 3783
Rain 2340
Horang2 881
Larva 458
BeSt 232
Mind 182
Movie 82
Mong 70
sas.Sziky 53
[ Show more ]
Barracks 47
Shinee 33
yabsab 32
soO 20
Free 19
Shine 13
Stormgate
NightEnD11
Dota 2
Gorgc12527
qojqva3028
League of Legends
Grubby3576
singsing2146
Counter-Strike
ScreaM2729
fl0m1597
Foxcn372
byalli239
edward86
Other Games
FrodaN1291
Beastyqt690
Fuzer 258
Trikslyr59
ZombieGrub22
Nathanias11
Organizations
Other Games
BasetradeTV26
StarCraft 2
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 16 non-featured ]
StarCraft 2
• intothetv
• AfreecaTV YouTube
• Kozan
• IndyKCrew
• LaughNgamezSOOP
• Migwel
• sooper7s
StarCraft: Brood War
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
Dota 2
• WagamamaTV515
League of Legends
• Nemesis5118
• Jankos1791
• TFBlade1053
Other Games
• imaqtpie899
• Shiphtur377
Upcoming Events
Korean StarCraft League
8h 54m
CranKy Ducklings
15h 54m
RSL Revival
15h 54m
ByuN vs Cham
herO vs Reynor
FEL
21h 54m
RSL Revival
1d 15h
Clem vs Classic
SHIN vs Cure
FEL
1d 17h
BSL: ProLeague
1d 23h
Dewalt vs Bonyth
Replay Cast
3 days
Sparkling Tuna Cup
3 days
The PondCast
4 days
[ Show More ]
Replay Cast
5 days
RSL Revival
5 days
Replay Cast
6 days
RSL Revival
6 days
Liquipedia Results

Completed

Proleague 2025-06-28
HSC XXVII
Heroes 10 EU

Ongoing

JPL Season 2
BSL 2v2 Season 3
BSL Season 20
Acropolis #3
KCM Race Survival 2025 Season 2
CSL 17: 2025 SUMMER
Copa Latinoamericana 4
Championship of Russia 2025
RSL Revival: Season 1
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
CCT Season 2 Global Finals
IEM Melbourne 2025

Upcoming

2025 ACS Season 2: Qualifier
CSLPRO Last Chance 2025
2025 ACS Season 2
CSLPRO Chat StarLAN 3
K-Championship
uThermal 2v2 Main Event
SEL Season 2 Championship
FEL Cracov 2025
Esports World Cup 2025
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.