Amicable numbers part 0

Working on this but need a reference copy to see while I am away from home. This lists up all combinations of x from y in order to work out amicable numbers.

#include <iostream>
#include <vector>

using namespace std;

/*
functions that gets passed two "ints"  x and y
and then returns a vector of vectors showing all the different
combinations of chosing x items from y.
This would then be called multiple times to generate indexes
used for fatorisation.

Think about actually creating lists or
something that could be created by the call - but
this is OK for the time being
*/

/*
combos passes integers from and total
and returns a vector of vectors of all combos
*/
vector< vector<unsigned int> > combos(unsigned int, unsigned int);

int main()
{
    //create a vector of vectors that contain ints
    vector < vector<unsigned int> > combinations = combos (10,10);

    for (unsigned int i = 0; i != combinations.size(); i++){
        unsigned int com_length = combinations[i].size();
        cout << "length of vector " << com_length << endl;
            for(unsigned int j = 0; j != com_length; j++){
                cout << combinations[i][j];
            }
            cout << endl;
    }
    return 0;
}




vector< vector<unsigned int> > combos(unsigned int from, unsigned int total){
    vector< vector<unsigned int> > vec;
    for (unsigned int i = 1; i != total; i++){
        vector <unsigned int> temp; //create temp new each time so you get rid of old one and start with a blank
        for (unsigned int j = 1; j != i; j++){
            temp.push_back(j);
        }
        vec.push_back(temp);
    }
    return vec;
}

scopes in c++

Some important points about scope here. This is taken from c++ in a nutshell but I wonder if it is exactly true or properly explained as the behavior is not quite what I expected from the description.

#include <iostream>
#include <ostream>

using namespace std;

/*
This is an abuse of the scope rules.  A scope is a region of code that can have
associated declarations and each declaration adds a name to a scope.  The compiler
works out what scope its in and then checks what names exist to use it.

Scopes include objects, functions, classes etc (stuff in curly {} brackets??).

Some scopes are named - e.g. functions, classes - some are unnamed e.g. statement blocks
such as if statements and for loops.

You can use the :: qualifier in front of a name to tell which scope to look at but most names
are unqualified so the computer has to work out what scope and then what name to look at.

With nested scopes NAMES IN INNERSCOPES CAN HIDE NAMES IN OUTER SCOPES!

The below will print out "in contrast ...10" 10 times and then print out both "x in this scope.."
and "in contrast..." 20 times.

For the first ten times the inner scope is not created so x is 10, then once x in the outscope
is more than 10 the inner scope x is created.
*/

int main()
{
    for (int i = 0; i < 30; i++){
        int x = 10;
        if (x < i){
            double x = 3.14;
            cout << "x in this scope is " << x << " and i is " << i << " and double x is " << x * 2 << endl;
        }
        cout << " in contrast x in this scope is " << x << " and i is " << i << endl;
    }
    return 0;
}

Work out the number of divisors

This program works out the first triangular number to have more than five hundred divisors.

It does so by going through all of the triangular numbers, working out their prime factors which are stored in a vector and then passing the vector to another routine that adds up the total number of each different prime which is stored in another vector.

The total number of divisors is then found by adding one to the number of vectors and then multiplying up.

It is worth thinking about how to reduce the number of iterations and a theory to work out a starting point that would make sure that you were covering the number of factors. The program could also work on seeing if there is some limit or distribution of number of divisors, perhaps related to the frequency of primes themselves.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    void factorize(vector<unsigned long long>&, unsigned long long); //
    void factors_out(vector<unsigned long long>&);
    unsigned long int count_factors(vector<unsigned long long>&);

    //target is the number you want to factorize
    unsigned long long target = 0;
    unsigned long int total_factors = 0;
    unsigned int tri = 1;

        while (total_factors < 501){
            target = target + tri;
            tri++;
            vector<unsigned long long> factor_list (1,1);
            factorize(factor_list, target);
            total_factors = count_factors(factor_list);
        }

    cout << "the answer is " << target;
    return 0;
}


//factorize is called recursively and modifies the vector, vec, that is passed by reference
void factorize (vector<unsigned long long>& vec, unsigned long long num){

    unsigned long long test_num = 2; //start with 2 to see if 2 is a factor
    unsigned long long limit_num = num - 1; //change this to square root later in order to speed up
    bool found_factor = false; //assume you have not found a factor

    while (test_num < limit_num){
        if (num % test_num == 0){
            found_factor = true;
            vec.push_back(test_num); //vec was passed by reference
            num = num/test_num;
            test_num = limit_num; //you found a factor, so move to end of while loop to finish it
            }
        test_num++;
    }
    if (found_factor == true){
        factorize(vec, num); //if you found a factor, re run with the number rounded down
    }
    else {
        vec.push_back(num); //you didn't find a factor, so the last number must be prime as well!
        return; //you didn't find another factor so finish
    }
}


void factors_out (vector<unsigned long long>& output_vec){

cout << "size of factor list " << output_vec.size() << endl;

    //size()method on vectors for number of elements
    unsigned int j = 0;
    while (j != output_vec.size()){
        cout << j << " one in the list " << output_vec[j] << endl;
        j++;
    }
    cout << "end of list"  << endl;
}


/*
simplify count factors by not actually recording the different primes but
instead create a vector that counts up the number of each different type of prime
and then calculates the number of divisors at the end
*/

unsigned long int count_factors (vector<unsigned long long>& count_vec){

    vector<unsigned int> primes_count; // a vector to store the count of different primes
    unsigned long long current_prime = count_vec[0];  //the first prime - this will always be 1
    unsigned int count_current_prime = 1; //we have one example of the first prime

    //make a vector that totals up the primes
    for (unsigned int k = 1; k != count_vec.size(); k++){
        if (count_vec[k] == current_prime) {
            count_current_prime++;
        }
        else {
            primes_count.push_back(count_current_prime);
            count_current_prime = 1;
            current_prime = count_vec[k];
        }
    }

    //now work out the number of factors
    unsigned long int total_factors = 1;
    for (unsigned int h = 0; h != primes_count.size(); h++) {
        total_factors *= (primes_count[h] + 1);
     }

    return total_factors;
}

Recursive factorisation passing vector by reference

This program helped solve Project Euler problem 3.

#include <iostream>
#include <vector>
#include <ctime>

using namespace std;

int main()
{
//prototype a function that passes an int and a vector of ints by reference and which returns a result that uses push_back on a vector
void factorize(vector<unsigned long long>&, unsigned long long);

//target is the number you want to factorize
unsigned long long target = 0;
cout << "what number should I factorize?" << endl;
cin >> target;

//factor_list is the vector that is passed by reference
vector<unsigned long long> factor_list (1,1);

unsigned int start = clock();

//call factorize function - note although you are passing by reference this is only mentioned in the prototype and function, not the function call!!
factorize(factor_list, target);

cout << "time taken in milliseconds "  << clock()-start;

cout << "size of factor list " << factor_list.size() << endl;

//size()method on vectors for number of elements
unsigned int j = 0;
while (j != factor_list.size()){
    cout << j << " one in the list " << factor_list[j] <<endl;
    j++;
}
    return 0;
}

//factorize is called recursively and modifies the vector, vec, that is passed by reference
void factorize (vector<unsigned long long>& vec, unsigned long long num){

    unsigned long long test_num = 2; //start with 2 to see if 2 is a factor
    unsigned long long limit_num = num - 1; //change this to square root later in order to speed up
    bool found_factor = false; //assume you have not found a factor

    while (test_num < limit_num){
        if (num % test_num == 0){
            found_factor = true;
            vec.push_back(test_num //vec was passed by reference
            num = num/test_num;
            test_num = limit_num; //you found a factor, so move to end of while loop to finish it
            }
        test_num++;
    }
    if (found_factor == true){
        factorize(vec, num); //if you found a factor, re run with the number rounded down
    }
    else {
        vec.push_back(num); //you didn't find a factor, so the last number must be prime as well!
        return; //you didn't find another factor so finish
    }
}

First prime number program

Program to calculate list of prime numbers - first 50,000 primes found in around 40 seconds.

#include <iostream>
#include <vector>

using namespace std;

//add_primes passes a complete list of prime numbers along with how many you want to add
//you can pass a vector "normally" - i.e. by value but this means that you copy the vector which is not so efficient
//you may want to pass by reference instead or also use const in order to prevent changes
//note you have to specify what type of vector as well or it just wont work at all!!
vector<unsigned long int> add_primes(vector<unsigned long int>, int);

int main()
{
    //set up some initial primes
    vector<unsigned long int> primes_list;
    primes_list.push_back(2);primes_list.push_back(3);primes_list.push_back(5);

    //ask how many primes you want to add to the list
    int extra_primes = 0;
    cout << "how many prime numbers to you want to add to the list? " << endl;
    cin >> extra_primes;

    primes_list = add_primes(primes_list,extra_primes);

    for (unsigned int i = primes_list.size()-1; i < primes_list.size();i++){
        cout << i+1 << "           " << primes_list[i] << endl;
    }

    return 0;
}

vector<unsigned long int> add_primes(vector<unsigned long int> primes, int add_ons){

    int found_new_primes = 0;
    int target;
    int primes_size;
    int primes_index;
    bool is_a_prime;

    primes_size = primes.size(); //starting number of primes
    target = primes[primes_size-1]; //starting point for search is largest prime in list


    while (found_new_primes < add_ons){

        target++; // increase target and then check if prime
        primes_index = 0; //move to start of list of primes
        is_a_prime = true; //assume target is prime until a divisor is found

        while (primes_index < primes_size){
            if ((target % primes[primes_index]) == 0) {
                is_a_prime = false; //found a divisor
                primes_index = primes_size; //found a divisor so move to the end of the primes list
            }
            primes_index++; //didnt find a divisor so move on to next prime in list
        }

        if (is_a_prime) {
            found_new_primes++;// increment as found a prime
            primes_size++; //increment as found a prime
            primes.push_back(target); //add a prime to the list
        }
    }
    return primes;
}

Introducing struct

Struct - structures - are similar to classes. Not sure of the difference. This also is the first time to use functions passing by address rather than by value - note the & syntax and that the function declaration and its definition both use the &. Note that using the const parameter can help reduce the risk of a variable being incorrectly modified when passed by reference.

#include <iostream>

using namespace std;

//Time has to be declared before its use in a function definition
 struct Time {
        int hour, minute;
        double second;
    };

//you don't put the parameter in the initial function declaration
// this function passes by address, not by value
void print_time(Time&);



int main()
{

  Time time = { 11, 59, 3.14159}; //you can assign numbers in order
  print_time(time);
    return 0;
}

the bool type and the const qualifier

Below are a few points about bools and const.

Note that bool is an integer type but const is a qualifier, used when declaring other types - e.g. an int or a short - as a constant value.

Advantages of the const qualifier over the #define directive are that (1) you can define the type of the constant at the time, (2) you can use c++s scoping rules to limit scope if you want (3) you can use the const value to declare the size of an array.

bool is_ready = true; //normal use of bool

int ans = true; //ans assigned 1
int promise = false; //promise assigned 0 

bool start = -100; //start assigned true - any NON ZERO value is converted to true
bool stop = 0; //stop is assigned false - only ZERO is converted to false

const int MONTHS = 12; //MONTHS is symbolic constant for 12

const int toes; //value of toes is UNDEFINED!
toes = 10; //too late - you have messed up and cannot modify it now

use of char

The program below about using char shows a little about how it works, but actually this is so boring I have skipped most of this stuff.

#include <iostream>

using namespace std;

int main()
{
    char ch = 'M'; //initialize ch as a char and assign M to it
    int i = ch; //store ch - a char - as an integer value
    cout << "the ascii code for i is " << i << endl;
    cout << "add 1 to the character code - i.e. to char ch and then assign to i" << endl;
    ch = ch + 1;
    i = ch;
    cout << "the ascii code for " << ch << " is " << i << endl;

    cout << "lets use cout.put() member function to display a char: " << endl;
    cout.put(ch);
    cout << endl << " and show cout.put() using a character constant " << endl;
    cout.put('X') << endl;
    cout << " done" << endl;
    cout << "note if you use cout.put() on a cout line it gets all messed up - see this - but with no syntax error " << endl;
    cout << "this is funnny " << cout.put(ch) << " funny ehh " << endl;
    return 0;
}

hex and octal and the cout stream

Use 0x in front of a number to put in hex and just 0 for octal. I can imagine a lot of bugs appear just using octal on things like string conversions etc!

The default for the cout stream is to assume that all feeds into the stream are in decimal, however you can change the number base through feeding a "hex" or "oct" to the stream - e.g. cout << hex << 42. hex (and oct?) are both part of the std namespace.

NOTE if you use a constant in a program - e.g. cout << "year = " << 1492 << endl; - then the 1492 would be stored as an int unless there was a reason not to do so (e.g. if the value is too large or you specify otherwise using some special suffixes).

You can place letters at the end of a numeric constant to specify the type - e.g. 22022LU or 22022UL - both unsigned long; use LL for long long etc.

#include <iostream>

using namespace std;

int main()
{
  int chest = 42; //decimal integer
  int waist = 0x42; //hexadecimal integer
  int inseam = 042; //octal integer

  cout << "monsiuer cuts a striking figure" << endl;
  cout << "chest = " << chest << " 42 in decimal" << endl;
  cout << "waist = " << waist << " 0x42 in hex" << endl;
  cout << "inseam = " << inseam << " 042 in octal" << endl;
    return 0;
}

example of signed and unsigned integers

This next code highlights the difference between signed and unsigned integers and shows how you can end up "going round the houses" when you go beyond the upper limits for the different variables  - with this happening for both signed and unsigned with different results.

 sam is the more normal signed integer while sue is unsigned (and hence can have much higher positive values but not negative values.



IMPORTANT NOTE - for unsigned integers the above "round the houses" behavior is guaranteed, but not for unsigned integers.


int main()
{
    short sam = SHRT_MAX;
    unsigned short sue = sam;

    cout << "Sam has " << sam << " dollars ans Sue has " << sue << " dollars deposited" << endl;
    cout << "add usd 1 to each account"  << endl << "now ";
    sam = sam + 1;
    sue = sue + 1;
    cout << "sam has "  << sam << "dollars " << "sue has "  << sue << " dollars - poor sam. Lets put to zero next" <<endl;
    sam = ZERO;
    sue = ZERO;
    cout << "now sam has " << sam << " dollars and sue has " << sue << " dollars" <<endl;
    cout << "take one dollar from each account" <<endl;
    sam = sam - 1;
    sue = sue - 1;
    cout << "now sam has " << sam << " dollars and sue has " << sue << " dollars" << endl;
    cout << "lucky sue" << endl;


    return 0;
}

Initilization of variables with braces {}

Braces are used for initialization of arrays but can also be used for single variables. Apparently this helps prevent type conversion errors. The advantage of extending {} is to provide some consistency between initializing ordinary variables and class variables in c++ syntax.

int hamburgers = {24}; //not an array but a single value variable
int emus{7}; //you don't have to use an = sign
int rocs = {}; //if braces are empty sets to zero
int psychics{} // zero and you don't have to use an =

climits and minimum or maximum values

This code does the following:

• introduces use of library header which includes some of the defined constants(?) for limits
• introduces the sizeof operator
• note in this program but this is a template about limits
• This is a great summary of fundamental types on cpp reference

Notes on syntax etc:

• sizeof operator puts brackets around type - e.g. sizeof (int) - but not around variables - e.g. sizeof n_short

Note that uses expressions such as "#define INT_MAX 32767" - which, on inclusion in the header file, acts as a kind of global find and replace for the values in the #define directive. You can use your own symbolic constants using the #define directive, but this is a relic of C. The better C++ method is to use const.

If you define a variable but don't initialize it then use it in a function the value is indeterminate and ends up as the value at whatever memory location you happen to have at that time.

#include <iostream>
#include <climits>

using namespace std;

int main()
{
    using namespace std;
    int n_int = INT_MAX;
    short n_short = SHRT_MAX; //these symbols defined in climits file
    long n_long = LONG_MAX;
    long long n_llong = LLONG_MAX;

    //sizeof operator yields size of type or of variable - NOT the maximum value it looks like
    cout << "int is " << sizeof (int) << " bytes" << endl;
    cout << "short is " << sizeof n_short << " bytes" << endl;
    cout << "long is " << sizeof n_long << " bytes" << endl;
    cout << "long long is " << sizeof n_llong << " bytes" << endl;
    cout << endl;

    cout << "maximum values" << endl;
    cout << "int: " << n_int << endl;
    cout << "short: " << n_short << endl;
    cout << "long: " << n_long << endl;
    cout << "long long: " << n_llong << endl;

    cout << "minimum int value: " << INT_MIN << endl;
    cout << "bits per byte: " << CHAR_BIT << endl;

    return 0;
}

Vectors

Vectors look very useful - basically seem to be arrays you can extend. C++ reference is here. This is an excellent tutorial - part 1. A few basic points:

• Indexing starts at zero and is done with [] brackets e.g. my_list[0]
• Looks like there are some methods taking you to the beginning and end of the list
• .set(value) one method to put stuff in an array
• .push_back(value) adds on to the end so may be more useful
• Can access with pointers as well as with []
• Can be used with iterators

Data types and their maximum values

The code below will give you the maximum values of items under c++11. Note you need a long long for Project Euler problem 3 Cpp reference also gives the types and the expression. However I don't really understand the syntax some_phrase::function() etc - remember to look out for this. Looks like there are many numeric_limits that can be accessed beyond max.

#include <iostream>
#include <limits>


using namespace std;

int main()
{
    cout << numeric_limits<unsigned long long>::max();
    return 0;
}

Excellent books list for c++

Great advice from this book list...

Converting data types - for example float to int

C++ produces warnings etc if you try and convert between data types - e.g. in something like int target = sqrt(number). However you can flag specific conversions to the compiler in the language.

This article explains why the preferred approach is to use is static_cast.

The explanation is rather obscure but seem to be related to the fact that what you are really doing is converting between different classes and while this is easy to understand between float and int for example could get more complicated at other times and there are some casting approaches that use some error checking - e.g. dynamic_cast. Well - at least that's my guess given the obscurity of the whole thing.

Syntax is here - with pointers to make things difficult:

MyClass *m = (MyClass *)ptr;
MyClass *m = static_cast<MyClass *>(ptr);
MyClass *m = dynamic_cast<MyClass *>(ptr);

Converting between strings and numbers

Something that should be easy seems to be more difficult than expected. Below as some conversion code not fully understood at the time of writing - i.e. have to understand the difference between ostringstream and stringstream.

#include <iostream>
#include <sstream>
#include <string>

using namespace std;

int main()
{

    int x = 1234;
    int y;
    string result;

    // converts integer to string which is held in result
    ostringstream conv;
    conv << x * 2;
    conv << 000; //gives a funny result - adds on a 0 at the end of the stream because we are only adding on zero as an integer, but after conversion....
    conv << "00"; //this does padd the result with two zeros - i.e similar to multiplying by 100
    cout << conv.str() << " converts number to string" << endl;
    result = conv.str();
    cout << result << " converted integer assigned to string variable" << endl;


    //takes the string created above and converts back to number
    stringstream string_to_num; // I tried this with conv
    string_to_num << result;

    string_to_num >> y;
    cout << y / 2000 << " output y and do numerical operations on y gets you back to x" << endl;

    return 0;
}

Euler question 2 sum of even fibonacci numbers

Learnt two points on this one, even though so simple. One of them has surely created a lot of errors!

When I first did this I declared the variable c but did not assign it a value before being used as part of a condition in a while loop (once in the loop was a + b). This was not spotted by the compiler but still compiled OK, then fell down and didn't work. The lesson seems to be always assign a value as soon as a variable is declared to avoid trouble spotting this type of problem later.

Second I had a warning in the syntax editor when comparing a signed and an unsigned integer. Did not cause a problem this time but easy to imagine it causing a problem in future

//============================================================================
// Name        : euler_q2_even_fibonacci.cpp
// Author      : mjl
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
using namespace std;

int main() {

	//you can declare multiple variables of the same type on one line
	//separate by commas but ; at the end
	unsigned int a, b, c;
	a = 1;
	b = 1;

	// this did not work when I did not include the below
	//but still compiled OK!
	//Probably something to do with the use in a while statement
	//comparison before being assigned a value!
	c = 0;


	unsigned int upper_limit = 4000000;

	//use modulo to allow more for not just even numbers
	int modulo = 2;

	unsigned int answer = 0;

	//need a while loop, not a for loop
	while (c < upper_limit) {
		c = a + b;
		if (c % modulo == 0){
			answer += c;
		}
		a = b;
		b = c;
	}

	cout << "the answer is " << answer;
	return 0;
}

Project Euler question 1 fizz buzz

This worked! Learnt for loops and if statements, compound cout, signed variables.

//============================================================================
// Name        : euler_q1_fizz_buzz.cpp
// Author      : mjl
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
using namespace std;

int main() {

	//you can create variable and assign a number at the same time
	//don't forget the ; after the variable declaration

	//don't foreget the ; inside the for loop declaration BUT...
	//you don't need a ; after the last increase statememt in the loop

	//make upper_limit unsigned for the hell of it
	unsigned int upper_limit = 1000;
	int answer = 0;

	// % and == same as python for modularity and comparison

	for (int x=1; x < upper_limit; x++) {
		if (x % 3 == 0){
			answer += x;
			continue;
		}
		if (x % 5 == 0){
			answer += x;
		}
	}

	//use a composite cout statement for the hell of it
	cout << "the answer is " << answer;

	return 0;
}

Posting code into blogger

Easiest way looks like simply cutting and pasting into this website. An example of the output is here...

//============================================================================
// Name        : euler_q1_fizz_buzz.cpp
// Author      : mjl
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
using namespace std;

int main() {
	cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!
	return 0;
}

Eclipse IDE set ups

Remember that each time you start a new project you also have to put some settings into the section below. This seems to have something to do with the linker, although can't remember what the linker does right now.