Converting Time in Seconds to Weeks, Days, Hours, Et Cetera

I found an interesting assignment in a C/C++ programming book I have. It was about converting seconds to minutes, and another about converting minutes/seconds to seconds. I decided to take that on, pushing it all the way to years. What this has actually become is an exercise in using modulo and division well.

The algorithm begins with calculating years, with each successive calculation containing all of the previous ones, and then changing the last operation from division to modulo. You have to do that in order to access the remainder left from the previous calculation. It’s more simple than it sounds. You only need to know ahead of time how many seconds are in a year, month, week, day, hour, and minute.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// ==================================================
// Programmer:  Jonathan Landrum
// Date:        20 February 2012
// ==================================================
// Program:     timeConverter.cpp
// Purpose:     Converts seconds input (integer) to
//              weeks, days, hours, minutes (etc.)
// Assumptions: 1.) Input is integer form. Floating
//                  point input will be rounded down
//                  to the nearest integer.
// ==================================================
 
#include <iostream>
using namespace std;
 
// --------------------------------------------------
// main():
// --------------------------------------------------
int main () {
 
	// Variables
	int years   = 0;
	int months  = 0; // 30 days
	int weeks   = 0;
	int days    = 0;
	int hours   = 0;
	int minutes = 0;
	int seconds = 0;
	unsigned long int input;
 
	// Introduce the program
	cout << endl;
	cout << "----------------------------" << endl;
	cout << "-      Time Converter      -" << endl;
	cout << "----------------------------" << endl;
	cout << endl;
	cout << "How many seconds to convert? ";
	cin  >> input;
 
	// Main processing loop
	years   = input / 31536000;
	months  = (input % 31536000) / 2592000;
	weeks   = ((input % 31536000) % 2592000) / 604800;
	days    = (((input % 31536000) % 2592000) % 604800) / 86400;
	hours   = ((((input % 31536000) % 2592000) % 604800) % 86400) / 3600;
	minutes = (((((input % 31536000) % 2592000) % 604800) % 86400) % 3600) / 60;
	seconds = ((((((input % 31536000) % 2592000) % 604800) % 86400) % 3600) % 60);
 
 
	// Return the results
	cout << "There are ";
	if (years != 0)
		cout << years << " years ";
 
	if (months != 0)
		cout << months << " months ";
 
	if (weeks != 0)
		cout << weeks << " weeks ";
 
	if (days != 0)
		cout << days << " days ";
 
	if (hours != 0)
		cout << hours << " hours ";
 
	if (minutes != 0)
		cout << minutes << " minutes ";
 
	if (seconds != 0) {
		if (input > 60)
			cout << "and " << seconds << " seconds ";
		else
			cout << seconds << " seconds ";
	} // End if. Will be rather uninpressive for input < 60.
 
	cout << "in " << input << " seconds." << endl;
 
	cout << endl;
	cout << "\\\\//_ Live long and prosper." << endl;
	cout << endl;
	return (0);
} // End main

Here’s a sample output from the program:

Time Converter

I’ve checked the output numerous times and it’s correct. The only thing it doesn’t do is Leap Year (as in calculating the date based on the Unix Epoch, for example), so it will return a higher number for days, weeks, etc. on those years.

Making correct Leap Year output could be done, but it would require inputting a starting year and calculating from there, and that’s not what this program does. It’s not a static time, for instance. It’s a general time, as in “how many days are in x seconds”. But the algorithm can be adapted for use in a time-since program. Perhaps I will write that one next.

~Jonathan

Calculating Factorials with an Iterative Method

I wrote yesterday about calculating factorials with a recursive function, and I mentioned that there was another method you could use to find the answer. I modified the program I wrote yesterday by completely removing the factorial() function and replacing the call to that function with a simple for loop.

There are times when a recursive approach is better, and there are times when an iterative approach is better. In this case, both come out with the answer in about the same time, but it’s up to you to determine which to use in which case. Obviously, if you have an algorithm that gets straight to the answer, choose that one! When I wrote about finding the difference of sums the other day, I skipped all the looping and got straight to the point with Euler’s summation algorithms. That was a one-step calculation, versus n cycles through a loop.

If not more efficient, the iterative approach is certainly more terse in this case. I cut out 22 lines of code in removing the factorial() function. But be cautious in pursuing terseness. Brevity and legibility are often inversely proportional to each other.

~Jonathan

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// ==================================================
// Programmer:  Jonathan Landrum
// Date:        16 February 2012
// ==================================================
// Program:     noFunctions.cpp
// Purpose:     Calculates up to 20!, sans functions.
// Assumptions: None.
// ==================================================
 
#include <iostream>
using namespace std;
 
// --------------------------------------------------
// main():
// Self-containing program
// --------------------------------------------------
int main () {
 
	// Variables
	long answer = 1;
	long response;
 
	// Introduce the program
	cout << endl;
	cout << "-----------------------------------------" << endl;
	cout << "-    Calculating Factorials up to 20!   -" << endl;
	cout << "-----------------------------------------" << endl;
	cout << endl;
	cout << "This program calculates factorials up to" << endl;
	cout << "20!. Larger factorials are impossible." << endl;
	cout << endl;
 
	// Get user response, then do some sanity checks
	do {
		cout << "Enter a positive integer less" << endl;
		cout << "than 21 to calculate: ";
		cin  >> response;
		cout << endl;
	} while (response < 0 || response > 20);
 
	// Calculate the answer
	for (int c = response; c > 1; c--)
		answer = answer * c;
 
	// Return the results
	cout << response << "! is " << answer << endl;
 
	return (0);
} // End main

Calculating Factorials with a Recursive Function

I initially set out with this program to find 100! (factorial), but integer space is simply not that large. (I’ve been doing a lot of big number things the last few days.) So, short of importing a library that can handle big numbers, we’ll have to settle for factorials less than 20.

The formal definition of factorial is “n! = the product as k goes from 1 to n of k”.

Factorial Definition

What that means is, that for every value of k as k goes from 1 to n, n! is the product of the multiplication of those values together. So 10! is 10 × 9 × 8 × … × 3 × 2 × 1, which is 3,628,800. We define 0! as 1 for a few reasons, mainly because it makes sense in combinatorics. If you think about it, it’s easy to see why: you can pick 0 items from an empty set only 1 way (by picking nothing at all).

Empty Set

As such, this program will calculate a factorial accurately from 0 to 20 inclusive, and will round real input to the lowest integer. To “factorial” non-integers, the Gamma Function is necessary, and it is essentially a generalization of factorial. The Gamma Function will work with both real and complex numbers. That is why this program rounds real input down to the nearest integer. Perhaps I’ll tackle the Gamma Function another day. ;~]

This program makes use of recursion to solve the factorial. You could also solve this particular problem by taking the user input as an integer and then using a for loop with that input as the counter, decrementing by 1 with each pass through the loop.

~Jonathan

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
// ==================================================
// Programmer:  Jonathan Landrum
// Date:        15 February 2012
// ==================================================
// Program:     20Factorial.cpp
// Purpose:     Calculates up to 20! using a function
// Assumptions: None.
// ==================================================
 
#include <iostream>
using namespace std;
 
// Function Prototypes
long factorial(long);
 
// --------------------------------------------------
// main():
// Calls factorial() and returns the answer
// --------------------------------------------------
int main () {
 
	// Variables
	long answer  = 0;
	int  response;
 
	// Introduce the program
	cout << endl;
	cout << "-----------------------------------------" << endl;
	cout << "-    Calculating Factorials up to 20!   -" << endl;
	cout << "-----------------------------------------" << endl;
	cout << endl;
	cout << "This program calculates factorials up to" << endl;
	cout << "20!. Larger factorials are impossible." << endl;
	cout << endl;
 
	// Get user response, then do some sanity checks
	do {
		cout << "Enter a positive integer less" << endl;
		cout << "than 21 to calculate: ";
		cin  >> response;
		cout << endl;
	} while (response < 0 || response > 20);
 
	// Main processing call
	answer = factorial(response);
 
	// Return the results
	cout << response << "! is " << answer << endl;
 
	return (0);
} // End main
 
// --------------------------------------------------
// factorial():
// Recursive function; makes repeated calls to itself
// in order to find n!. Works for up to 20!.
// --------------------------------------------------
long factorial(long in) {
 
	// Variables
	long out;
 
	// Run recursive calculation
	if (in == 0 || in == 1)
		out = 1;
	else
		out = in * factorial (in - 1);
 
	// Return the results
	return out;
}

Happy Valentine’s Day (in C++)

We wrote this program in C/C++ yesterday in honor of St. Valentine’s Day. It prints a simple ASCII heart with a geeky poem written above it:

Roses are #FF0000;
    Violets are #0000FF;
All my base
    Are belong to you!

Valentine's Day Heart

I showed it to my wife last night, and she was happy to receive it. But be warned, it’s no stand-in for actual flowers and candy.

~Jonathan

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
// Happy St. Valentine's Day!
 
#include <iostream>
using namespace std;
 
int main() {
	int ht;
	int row;
	int index;
	int topHt;
	int initSpace;
	do {
		cout << "Enter the height of your heart: ";
		cin  >> ht;
		if (ht < 3) {
			cout << "have a bigger heart!" << endl;
		} // end if
	} while (ht < 3);
 
	// get it down a couple spaces, and center a message to your Valentine
	cout << endl << endl;
	cout << "                               Roses are #FF0000;" << endl;
	cout << "                                   Violets are #0000FF;" << endl;
	cout << "                               All my base" << endl;
	cout << "                                   Are belong to you!" << endl << endl;
 
	// draw top of the heart
	topHt = ht + 1;
	initSpace = 40 - 2 * ht;
 
	// loop for each top row
	for (row = 2; row < topHt; row++) {
 
		// loop for centering spaces
		for (index = 0; index < initSpace; index++)
			cout << " ";
 
		// loop for initial spaces
		for (index = 0; index < (topHt - row); index++)
			cout << " ";
 
		// loop for right atrium (left side)
		for (index = 0; index < (row * 2 - 1); index++)
			cout << "*";
 
		// loop for aorta :~]
		for (index = 0; index < (2 * (topHt - row) - 1); index++)
			cout << " ";
 
		// loop for left atrium (right side)
		for (index = 0; index < (row * 2 - 1); index++)
			cout << "*";
 
		cout << endl;
	} // end main for
 
	// draw bottom of the heart
	ht = ht * 2 + 1;
	for (row = ht; row > 0; row--) {
 
		// loop for centering spaces
		for (index = 0; index < initSpace; index++)
			cout << " ";
 
		// loop for spaces
		for (index = 0; index < (ht - row); index++)
			cout << " ";
 
		// loop for asterisks
		for (index = 0; index < (row * 2 - 1); index++)
			cout << "*";
 
		cout << endl;
	} // end main for
 
	// add some more spacing at the end for looks
	cout << endl << endl;
 
	return 0;
 
} // end main

Adding the Prime Numbers Less Than 2,000,000

I attempted to solve this problem using Fortran, because I have a soft spot for that language. However, Fortran is limited in integer reproduction. The largest number produceable using a 32-bit integer data type is 2,147,483,647. The sum of primes greater than 2,000,000, however, is much larger than that. So what I noticed first was my number was wrong. To find where the problem was, I decided to print my running sum as it was tallying the numbers. I then noticed that it went negative quite a few times, which means it ran out of space to hold the number. I knew then what I had to do: convert it to C++ and change the integer to a long integer, which has a 64-bit space on C++. Doing that solved my problem, and I came out (finally) with the correct answer.

~Jonathan

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
// ==================================================
// Programmer:  Jonathan Landrum
// Date:        10 February 2012
// ==================================================
// Program:     sumOfPrimes.cpp
// Purpose:     Adds together the prime numbers less
//              than 2,000,000.
// Assumptions: None.
// ==================================================
 
#include <iostream>
using namespace std;
 
// --------------------------------------------------
// Function prototypes
// --------------------------------------------------
bool prime(int);
 
 
// --------------------------------------------------
// main():
// Calls the prime() function to determine which
// numbers are prime, and then adds them to the sum.
// --------------------------------------------------
int main () {
 
	// ------------------------------------------
	// Variables
	// ------------------------------------------
	int  counter = 1;
	long sum = 0;
 
	// ------------------------------------------
	// Introduce the program
	// ------------------------------------------
	cout << endl;
	cout << "---------------------------" << endl;
	cout << "-      Sum of Primes      -" << endl;
	cout << "---------------------------" << endl;
	cout << endl;
	cout << "This program adds the prime" << endl;
	cout << "numbers less than 2,000,000" << endl;
	cout << endl;
 
	// ------------------------------------------
	// Main processing loop
	// ------------------------------------------
	while (counter < 2000000) {
		if (prime(counter))
			sum += counter;
		counter += 2;
	} // End while
 
	// ------------------------------------------
	// Return the results
	// ------------------------------------------
	cout << sum << endl;
	cout << "-----------------------------" << endl;
	cout << "\\\\//_ Live long and prosper." << endl;
	return (0);
} // End main
 
 
// --------------------------------------------------
// prime():
// Determines if a number is prime
// --------------------------------------------------
bool prime (int n) {
 
	// Variables
	bool result;
	int  i;
 
	// Do work
	if (n <= 1) {
		result = false; // 1 is not prime
 
	} else if ((n == 2) || (n == 3)) {
		result = true; // Hard code 2 and 3
 
	} else if (n % 2 == 0) {
		result = false; // Get rid of evens
 
		/* All other cases are out, so now we check
		 to see if n is divisible by the odd
		 numbers from 3 on. */
	} else {
		i = 3;
		result = true; // Assume it's prime, then prove
 
		while (true) {
			/* If i^2 is not a root of n, or if
			 n % i == 0. (Won't be larger than
			 the square.) */
			if ((i * i > n) || (n % i == 0))
				break;
			i += 2; // Iterate by 2 to get odds
		} // End while
 
		// Record the answer
		if (i * i > n)
			result = true;
		else
			result = false;
	} // End if
 
 
	// Return the answer
	return result;
}

Computing the nth Prime

I wrote a program a while back that found all the primes in a list, and it used Fortran to do it. At the time I first wrote this program, one of my instructors challenged me to a race to find the nth prime, which I couldn’t do with that program. So, I’ve decided to rewrite the program altogether — this time in C++ — and can now say I am able to find any one of the prime numbers on command. Since the prime in question was the 1,000,000th one, I found that one after making sure the program works: 15,485,863. One thing I’ve noticed is that writing this in C++ has made the program faster. It only took a couple seconds to return the 1,000,000th prime, which is no small feat for a laptop. Now to take on that professor. :~]

~Jonathan

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
// ==================================================
// Programmer:  Jonathan Landrum
// Date:        6 February 2012
// ==================================================
// Program:     nthPrime.cpp
// Purpose:     Finds the nth prime number.
// Assumptions: 1.) Input is in natural number form
//                  (primes are natural numbers.)
// ==================================================
 
#include <iostream>
using namespace std;
 
// --------------------------------------------------
// Function Prototypes
// --------------------------------------------------
bool prime (int);
 
 
// --------------------------------------------------
// main():
// Calls the prime() function to find primes, and
// returns the nth prime (as specified by the user.)
// --------------------------------------------------
int main () {
 
	// ------------------------------------------
	// Declare variables, not war
	// ------------------------------------------
	int counter = 1;
	int n = 0;
	int out = 0;
 
	// ------------------------------------------
	// Introduce the program
	// ------------------------------------------
	cout << endl;
	cout << "------------------------------" << endl;
	cout << "-    nth Prime Calculator    -" << endl;
	cout << "------------------------------" << endl;
	cout << endl;
	cout << "This program finds the nth" << endl;
	cout << "prime number." << endl;
	cout << endl;
	cout << "Which prime would you like to" << endl;
	cout << "find? Enter an integer: ";
	cin  >> n;
	cout << endl;
 
	// ------------------------------------------
	// Main processing loop
	// ------------------------------------------
	out = 2;
	while (counter < n) {
		out++;
		if (prime(out)) {
			counter++;
		} // End if
	} // End while
 
	// ------------------------------------------
	// Return the results
	// ------------------------------------------
	cout << out << " is the " << n << "th prime." << endl;
 
	return (0);
} // End main
 
 
// --------------------------------------------------
// prime():
// Determines if a number is prime
// --------------------------------------------------
bool prime (int n) {
 
	// Variables
	bool result;
	int  i;
 
	// Do work
	if (n <= 1) {
		result = false; // 1 is not prime
 
	} else if ((n == 2) || (n == 3)) {
		result = true; // Hard code 2 and 3
 
	} else if (n % 2 == 0) {
		result = false; // Get rid of evens
 
	/* All other cases are out, so now we check
	   to see if n is divisible by the odd
	   numbers from 3 on. */
	} else {
		i = 3;
		result = true; // Assume it's prime, then prove
 
		while (true) {
			/* If i^2 is not a root of n, or if
			   n % i == 0. (Won't be larger than
			   the square.) */
			if ((i * i > n) || (n % i == 0))
				break;
			i += 2; // Iterate by 2 to get odds
		} // End while
 
		// Record the answer
		if (i * i > n)
			result = true;
		else
			result = false;
	} // End if
 
 
	// Return the answer
	return result;
}

Fun With Diamonds

I was googling for programming challenges today and ran across one that was more than twenty years old. It was an old scan of an assignment a fellow posted about his days in college taking Pascal. The idea behind the challenge is to write a program that takes user input for size, and builds a diamond out of characters to the size specified.

Write a program which draws a diamond of the form illustrated below. The letter which is to appear at the widest point of the figure (E in the example) is to be specified as input data.

Diamond Challenge

Problem is, I’d never made a diamond program before. The closest I’ve come was a Christmas tree program, which replaces the bottom of the diamond with a trunk. It’s a bit easier to make because you don’t have to think about reversing your algorithm.

So to start this project, I first built a standard diamond program. These types of programs ask for an integer, and build a diamond out of asterisks with the middle row containing the specified number of asterisks.

I then modified the program to be a “hollow” diamond, with the middle asterisks being replaced by space characters. After mastering that, I felt confident in my algorithm to take on the character diamond. It proved only slightly more challenging than the hollow diamond, really just replacing the calls to print an asterisk with a call to print a character from an array which stored all the letters. Here’s a screen capture of an example output:

Character Diamond

All in all, I am very well pleased with the outcome of this program. I tested it with every letter, and it performs flawlessly every time. It may not be the shortest algorithm to produce the character diamond, but it’s mine.

~Jonathan

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
// ==================================================
// Programmer:  Jonathan Landrum
// Date:        4 February 2012
// ==================================================
// Program:     char-diamond.cpp
// Purpose:     Takes user input of one character and
//              returns a diamond of that size.
// Assumptions: 1.) Input is a single letter (char).
//                  Any other input will return un-
//                  expected results.
// ==================================================
 
#include <iostream>
#include <string>
 
using namespace std;
 
// --------------------------------------------------
// Global Variables
// --------------------------------------------------
char letter[26] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
	           'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};
 
// --------------------------------------------------
// main():
// Does ALL the things!
// --------------------------------------------------
int main () {
 
	// ------------------------------------------
	// Declare variables, not war
	// ------------------------------------------
	char in;
	int  counter;
	int  input;
	int  level;
	int  spaces;
 
	// ------------------------------------------
	// Introduce the program
	// ------------------------------------------
	cout << endl;
	cout << "---------------------------" << endl;
	cout << "-    Character Diamond    -" << endl;
	cout << "---------------------------" << endl;
	cout << endl;
	cout << "             A" << endl;
	cout << "            B B" << endl;
	cout << "           C   C" << endl;
	cout << "          D     D" << endl;
	cout << "         E       E" << endl;
	cout << "          D     D" << endl;
	cout << "           C   C" << endl;
	cout << "            B B" << endl;
	cout << "             A" << endl;
	cout << endl;
	cout << "This program asks for a" << endl;
	cout << "character, and returns a" << endl;
	cout << "diamond of that size." << endl;
	cout << endl;
 
	// ------------------------------------------
	// Main processing loop
	// ------------------------------------------
	cout << "Enter a single letter for the size of your diamond: ";
	cin  >> in;
 
	input = toupper(in) - 64;
	input = input * 2 - 1;
	counter = 1;
	level = 0;
 
	while (counter < input) {
		if (input % 2 == 0)
			spaces = ((input - counter) / 2) + 1;
		else
			spaces = (input - counter) / 2;
 
		for (int c = 0; c < spaces; c++)
			cout << " ";
 
		cout << letter[level];
 
		if (counter == 1)
			spaces = 0;
		else
			spaces = counter - 2;
 
		for (int i = 0; i < spaces; i++)
			cout << " ";
 
		if (counter != 1)
			cout << letter[level] << endl;
		else
			cout << endl;
 
		counter += 2;
		level++;
	} // End while
	while (counter > 0) {
		if (input % 2 == 0)
			spaces = ((input - counter) / 2) + 1;
		else
			spaces = (input - counter) / 2;
 
		for (int j = 0; j < spaces; j++)
			cout << " ";
 
		cout << letter[level];
 
		if (counter == 1)
			spaces = 0;
		else
			spaces = counter - 2;
 
		for (int n = 0; n < spaces; n++)
			cout << " ";
 
		if (counter != 1)
			cout << letter[level] << endl;
		else
			cout << endl;
 
		counter -= 2;
		level--;
	} // End while
 
	return (0);
} // End main

Finding the Difference of Sums using C++

Someone asked online what the difference was between the sum of the squares and the square of the sums. For instance, if you were to add all the natural numbers from 1 to 10, and then square it, would it be larger, smaller, or the same size if you squared each integer first and then added them?

12 + 22 + 32 + … + 82 + 92 + 102 (Sum of the squares)
(1 + 2 + 3 + … + 8 + 9 + 10)2 (Square of the sums)

At first glance, this seems like a fine job for a couple loops, or perhaps recursion. But there’s actually a much more efficient way to go about this problem, and the answer is brought to us by a fine mathematician named Leonhard Euler.

Euler is one of the men responsible for bringing us Calculus (he actually is responsible for more of Calculus than Newton) and one of the topics discussed in the second semester of Single-variable Calculus is Summation. Using these summation algorithms, it is possible to do some very intriguing calculations without going through the rote process of cycling through the list.

For a short set such as the first ten integers, it’s not a problem. But suppose the question was of the first ten million integers? That would take a looping algorithm a long time. But it would take almost exactly the same time as doing the first 10 using Euler’s algorithms.

Algorithm for summing integers:
Algorithm for summing integers

Algorithm for summing squares of integers:
Algorithm for summing squares of integers

With these algorithms, it’s trivial to find the answer to the problem at hand. Nevertheless, I’ve written a program anyway, if for no other reason than to show how to use these algorithms.

~Jonathan

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// ==================================================
// Programmer:  Jonathan Landrum
// Date:        3 February 2012
// ==================================================
// Program:     difference.cpp
// Purpose:     Finds the difference between the sum
//              of the squares and the square of the
//              sums of the first 100 integers.
// Assumptions: None.
// ==================================================
 
#include <iostream>
using namespace std;
 
// --------------------------------------------------
// main():
// Does ALL the things!
// --------------------------------------------------
int main () {
 
	// ------------------------------------------
	// Declare variables, not war
	// ------------------------------------------
	int sumSquares;
	int squareSums;
	int difference;
 
	// ------------------------------------------
	// Introduce the program
	// ------------------------------------------
	cout << endl;
	cout << "--------------------------------" << endl;
	cout << "-    Finding the Difference    -" << endl;
	cout << "--------------------------------" << endl;
	cout << endl;
	cout << "This program seeks to find the" << endl;
	cout << "difference between the sum of" << endl;
	cout << "squares and the square of the" << endl;
	cout << "sums." << endl;
	cout << endl;
 
	// ------------------------------------------
	// Main processing loop
	// ------------------------------------------
 
	/* ******************************************
	   Yes, you can use loops here, but why would
	   you want to? There are already algorithms
	   for finding these answers.
	   ****************************************** */
 
	sumSquares = 100 * 101 * 201 / 6;     // Algorithm for summing squares:  n(n+1)(2n+1)/6
	squareSums = 100 * 101 / 2;           // Algorithm for summing integers: n(n+1)/2
	squareSums = squareSums * squareSums; // Now squaring it
 
	if (sumSquares - squareSums > 0) {
		difference = sumSquares - squareSums;
		cout << "sumSquares is larger. (" << sumSquares << ")" << endl;
	} else {
		difference = squareSums - sumSquares;
		cout << "squareSums is larger. (" << squareSums << ")" << endl;
	} // End if
 
 
	// ------------------------------------------
	// Return the results
	// ------------------------------------------
	cout << difference << " is the difference between " << squareSums << " and " << sumSquares << endl;
	return (0);
} // End main

Finding the Smallest Integer Evenly Divisible by all the Numbers from 1 to 20

I found this programming assignment online today. It posits that 2,520 is the smallest number evenly divisible by all the natural numbers from 1 to 10. The question is, what is the smallest number evenly divisible by all the natural numbers from 1 to 20? It seemed like the best idea to me to save the answers in a boolean array, one cell for each of the numbers from 1 to 20, and if every answer is true, then we have our number. I tested it, got the correct result, and the answer is surprisingly large. Suffice it to say, it took a minute to get there.

~Jonathan

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
// ==================================================
// Programmer:  Jonathan Landrum
// Date:        2 February 2012
// ==================================================
// Program:     evenlyDivisible.cpp
// Purpose:     Finds the smallest number evenly
//              divisible by all the natural numbers
//              from 1 to 20.
// Assumptions: None.
// ==================================================
 
#include <iostream>
 
using namespace std;
 
// --------------------------------------------------
// main():
// Does ALL the things!
// --------------------------------------------------
int main () {
 
	// ------------------------------------------
	// Declare variables, not war
	// ------------------------------------------
	bool answers[20];
	bool divisible = false; // Not true for 20
	int  number    = 20;    // But logical place to start
 
	// ------------------------------------------
	// Introduce the program
	// ------------------------------------------
	cout << endl;
	cout << "----------------------------" << endl;
	cout << "-     Evenly Divisible     -" << endl;
	cout << "----------------------------" << endl;
	cout << endl;
	cout << "This program checks to find" << endl;
	cout << "the smallest number that is" << endl;
	cout << "evenly divisible by all the" << endl;
	cout << "integers from 1 to 20." << endl;
	cout << endl;
	cout << "Processing..." << endl;
 
	// ------------------------------------------
	// Main processing loop
	// ------------------------------------------
	while (divisible == false) {
		for (int counter = 1; counter <= 20; counter++) {
			if (number % counter == 0) {
				answers[counter - 1] = true;
			} else {
				answers[counter - 1] = false;
			} // End if
		} // End for
		if (answers[0]  == true &&
		    answers[1]  == true &&
		    answers[2]  == true &&
		    answers[3]  == true &&
		    answers[4]  == true &&
		    answers[5]  == true &&
		    answers[6]  == true &&
		    answers[7]  == true &&
		    answers[8]  == true &&
		    answers[9]  == true &&
		    answers[10] == true &&
		    answers[11] == true &&
		    answers[12] == true &&
		    answers[13] == true &&
		    answers[14] == true &&
		    answers[15] == true &&
		    answers[16] == true &&
		    answers[17] == true &&
		    answers[18] == true &&
		    answers[19] == true) {
			divisible = true;
		} else {
			number++;
		} // End if
	} // End while
 
	// ------------------------------------------
	// Return the results
	// ------------------------------------------
	cout << "The answer is " << number << endl;
 
	return (0);
} // End main

Adding the Even Numbers of the Fibonacci Sequence

Suppose you want to find all the even numbers in the Fibonacci Sequence less than, say, 4,000,000, and you want to add them together. This can easily be done with a couple of methods in C++ or the language of your choice.

The idea behind the Fibonacci sequence is to add the previous two numbers together to get the current number. So you get 0, 1, 1, 2, 3, 5, 8, 13, 21 and so on, ad infinitum. If we were to take only the even ones and add them, what would you get? In the case of the previous list, only 2 and 8 are even, so you would get 10. This program runs the computation to 4,000,000 and it gave me the answer in less than one second.

~Jonathan

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
// ==================================================
// Programmer:  Jonathan Landrum
// Date:        1 February 2012
// ==================================================
// Program:     evenFibonacci.cpp
// Purpose:     Summs the even numbers in the
//              Fibonacci sequence that are less
//              than 4,000,000.
// Assumptions:	None.
// ==================================================
 
#include <iostream>
#include <string>
 
using namespace std;
 
// --------------------------------------------------
// Function prototypes
// --------------------------------------------------
int fib(int);
 
// --------------------------------------------------
// main():
// Does ALL the things!
// --------------------------------------------------
int main () {
 
	// ----------------------------------------------
	// Declare variables, not war
	// ----------------------------------------------
	int c = 0;
	int number;
	int sum = 0;
 
	// ----------------------------------------------
	// Introduce the program
	// ----------------------------------------------
	cout << endl;
	cout << "-----------------------------" << endl;
	cout << "-      Even Fibonaccis      -" << endl;
	cout << "-----------------------------" << endl;
	cout << endl;
	cout << "1, 2, 3, 5, 8, 13, 21, 34,..." << endl;
	cout << endl;
	cout << "This program calculates the" << endl;
	cout << "Fibonacci sequence and adds" << endl;
	cout << "the even ones less than" << endl;
	cout << "4,000,000 together." << endl;
 
	// ----------------------------------------------
	// Main processing loop
	//
	// There are a few different ways to accomplish
	// this. I chose this algorithm because it made
	// sense to me. You can also get rid of the first
	// "if" by putting "number < 4000000" in the
	// while test, and moving "number = fib(c)" to
	// after "c++".
	//
	// This algorithm returns the answer in <1 second
	// on my laptop.
	// ----------------------------------------------
	while (true) {                 // Need to keep it going
		number = fib(c);
		if (number >= 4000000) // until we can break
			break;
		if (number % 2 == 0)
			sum += number;
		c++;
	} // End while
 
	// ----------------------------------------------
	// Return the results
	// ----------------------------------------------
	cout << sum << endl;
	cout << "-----------------------------" << endl;
	cout << "\\\\//_ Live long and prosper." << endl;
	return (0);
} // End main
 
// --------------------------------------------------
// fib():
// Calculates the integer in the Fibonacci sequence
// at the input space. 2 returns 1, 7 returns 13, ...
// --------------------------------------------------
int fib (int in) {
	int out;
 
	if (in == 0 || in == 1) {
		out = in;
	} else {
		out = (fib(in-2) + fib(in-1));
	} // End if
 
	return out;
} // End fib