# QuantNet Coding Project

#### Mr Doe

These problem are fine, but I think us (wannabe) quants can do better! I found a nice problem related to probability (cause quant.finance (\approx) probability). Here it goes;

You are given a unique investment opportunity.
Starting with £1 of capital, you can choose a fixed proportion, f, of your capital to bet on a fair coin toss repeatedly for 1000 tosses.
For example, if f = 1/4, for the first toss you bet £0.25, and if heads comes up you win £0.5 and so then have £1.5. You then bet £0.375 and if the second toss is tails, you have £1.125.
Choosing f to maximize your chances of having at least £1,000,000,000 after 1,000 flips, what is the chance that you become a billionaire?
All computations are assumed to be exact (no rounding), but give your answer rounded to 12 digits behind the decimal point in the form 0.abcdefghijkl.

This is problem 267. I'm looking forward to hearing your thoughts.

#### John Jurcevic

Problem 2 - C#

Translating Bobby's code into C# using lambda expressions, query methods and anonymous types (because they are cool and I'm trying to learn this stuff).

C++:
Func<int, int> fib = x =>
{
var f = 0.5 * (1.0 + Math.Sqrt(5.0));
return (int) (Math.Sqrt(0.2) * (Math.Pow(f, x) - Math.Pow(1.0 - f, x)));
};

Console.WriteLine(
Enumerable.Range(1, 15)
.Where(x => fib(3 * x) < 4000000)
.Aggregate(0, (total, x) => total + fib(3 * x))
);

#### Joy Pathak

##### Swaptionz
These problem are fine, but I think us (wannabe) quants can do better! I found a nice problem related to probability (cause quant.finance (\approx) probability). Here it goes;

You are given a unique investment opportunity.
Starting with £1 of capital, you can choose a fixed proportion, f, of your capital to bet on a fair coin toss repeatedly for 1000 tosses.
For example, if f?=?1/4, for the first toss you bet £0.25, and if heads comes up you win £0.5 and so then have £1.5. You then bet £0.375 and if the second toss is tails, you have £1.125.
Choosing f to maximize your chances of having at least £1,000,000,000 after 1,000 flips, what is the chance that you become a billionaire?
All computations are assumed to be exact (no rounding), but give your answer rounded to 12 digits behind the decimal point in the form 0.abcdefghijkl.

This is problem 267. I'm looking forward to hearing your thoughts.

Lol I think one of the points of the simpler problems was for everyone learning to start off from the basics and gradually build up after getting a good grip on syntax and flow and so on.

I am going to try your problem though on python.

#### koupparis

##### Carpe noctum
I thought so too, but it is actually 21162960.

It's a weird... Here is what I did

It is basically a question of lcm(11,12,...20). So find prime factorization:
11: 11
12: 2*2*3
13: 13
14: 2*7
15: 3*5
16: 2*2*2*2
17: 17
18: 2*3*3
19: 19
20: 2*2*5

So LCM SHOULD be 2^4 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19 which is 232792560. HOWEVER.

232792560 a multiple of 11^2. So the LCM is 232792560/11, which is 21162960
How can 232792560 be divisible by 11^2 when you only have one 11 in its prime factorization? The answer is still 232792560

#### goodstudent

How can 232792560 be divisible by 11^2 when you only have one 11 in its prime factorization? The answer is still 232792560

O.M.G. I am an idiot. I didn't keep enough sig figs so I thought it was divisible by 121 haha.

But yeah, the answer is 232792560

#### brokebroke

Prelude> sum [x | x<-[1..999], x mod 3 ==0 || x mod 5 ==0]
233168

#### Joy Pathak

##### Swaptionz
There are several ways to write the number 1/2 as a sum of inverse squares using distinct integers.

For instance, the numbers {2,3,4,5,7,12,15,20,28,35} can be used:

In fact, only using integers between 2 and 45 inclusive, there are exactly three ways to do it, the remaining two being: {2,3,4,6,7,9,10,20,28,35,36,45} and {2,3,4,6,7,9,12,15,28,30,35,36,45}.

How many ways are there to write the number 1/2 as a sum of inverse squares using distinct integers between 2 and 80 inclusive?

Just came across this. Thought I would toss it here if people are still interested.

#### pathfinder

solution for problems 1
=============================================================
Problem 1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.

----------------------------------------
#include<iostream.h>

int main()
{
int sum=0;
for (int i=1; i<1000 ; i++)
{
if((i%3==0) || (i%5==0))
{

sum+=i;
}
}
cout<<"sum is "<<sum<<endl;
return 1;
}

---------- Post added at 04:13 AM ---------- Previous post was at 04:06 AM ----------

solution for problems 2
=============================================================

Problem 2
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...​
Find the sum of all the even-valued terms in the sequence which do not exceed four million.

--------------------------------------------------------------
#include<iostream.h>

int main()
{
int f0=1,f1=2,f2,sum=0;

while( (f2=f0+f1) < 4000000)
{
if(f1%2==0)sum+=f1;
f0=f1;
f1=f2;

}
cout<<"Sum is "<<sum<<endl;
return 1;

}

---------- Post added at 04:31 AM ---------- Previous post was at 04:13 AM ----------

solution for problems 4
=============================================================

Problem 4
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91
99.
Find the largest palindrome made from the product of two 3-digit numbers.

------------------------------------------------------------------------------------------------------------

#include<iostream.h>

int rev(int num){

int r=0;
while(num)
{
r=r*10+num%10;
num=num/10;
}
return r;
}

int main()
{
int n;

int max=0,i_k=0,j_k=0;
for(int i=999; i>100; i--)
for(int j=999;j >100; j--)
{
n=i*j;
if(n<=max)
{
break;
}
if(n ==rev(n))
{
// cout<<"n is "<<n<<endl;
if(n>=max)
{
max=n;
i_k=i;
j_k=j;
}
}
}
cout<<i_k<<" *"<<j_k<<"= "<<max;
return 1;

}

---------- Post added at 04:36 AM ---------- Previous post was at 04:31 AM ----------

solution for problems 5
=============================================================
Problem 5
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

---------------------------------------------------------------------------------
#include<iostream.h>

int find_lcm(int x,int y)
{
int a,lcm;
if(y>x){
a=x;
x=y;
y=a;
}

/*x is the larges number;*/
lcm=x;
while(lcm%y != 0)
{
lcm+=x;

}

return lcm;
}

int main()
{

int lcm=1,t,quit=0;
for(int i=2;i<=20 ; i++)
{
//find LCM
lcm=find_lcm(lcm,i);
}
cout<<"Ans : "<< lcm<<endl;
return 1;
}

#### Sporkman

Problem 4:

Written in Sporkl:

C++:
int max_prod = 999*999;

int i, j;

for ( i=max_prod; i>0; --i )
{
if ( is_palindrome(i) )
{
for ( j=999; j>=100; --j )
{
float fi = i;
float f = fi / j;
if ( f>999 )
{
break;
}
if ( f-floor(f)==0 )
{
print("The answer is " + str(i) + " = " + str(j) + " * " + str(i/j) + "\n");
return;
}
}
}
}

function byte is_palindrome ( int i )
{
string s = str(i);
int j;
int len = length(s);
for ( j=0; j<len/2; ++j )
{
if ( get_char(s,j)!=get_char(s,len-j-1) )
{
return false;
}
}
return true;
}
Result:
The answer is 906609 = 993 * 913

#### pathfinder

oops how can I forget problem 3

Solution to problem 3
======================================
Problem 3
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

----------------------------------------------------------------------------
#usage: perl findPrime.pl <number>

#the code is in perl

sub isPrime{
my $n=shift; if($n eq 2 or $n eq 3 or$n eq 1){
return 1;
}
if(($n%6 ne 1) and ($n%6 ne 5))
{
return 0;
}
my $sq=sqrt($n);
$sq=~ s/\.\d*//g; for(my$i =2 ; $i<=$sq ; $i++) { if($n%$i eq 0){ return 0; } } return 1; } sub findPrimeFactor{ my$n=shift;
my $sq=sqrt($n);
$sq=~ s/\.\d*//g; my$c=0; $tmp=4; print "Finding the highest prime...\n"; for(my$i =$sq ;$i >1; $i--) { if(isPrime($i))
{
$c++; if($n%$i eq 0) { if(($tmp=$n/$i) > $i and isPrime($tmp)){
return $tmp; } else{ return$i;
}

}
if($c%20 eq 0) { print "."; if($c%200 eq 0){
print "\n";
}
}
}
}
return 1;
}

if($#ARGV < 0) { print "usage : perl findPrime.pl <number>\n"; exit 1; } my$t1=time;

my $hpf=findPrimeFactor($ARGV[0]);
my $t2=time;$t2=$t2-$t1;

print "\n\tHighest Prime Factor of $ARGV[0] is$hpf....\n";
print "\tThis operation took $t2 seconds...\n"; --------------------------------------------------------------------------------------------------- This program takes 18 seconds on my system to find the highest prime of 600851475143 Answer: 6857 #### iddqd I'd take another look at it mine ran in 0.01 seconds (in python) #### pathfinder Solution for problem 267 ---------- Post added at 11:50 PM ---------- Previous post was at 11:31 PM ---------- These problem are fine, but I think us (wannabe) quants can do better! I found a nice problem related to probability (cause quant.finance (\approx) probability). Here it goes; You are given a unique investment opportunity. Starting with £1 of capital, you can choose a fixed proportion, f, of your capital to bet on a fair coin toss repeatedly for 1000 tosses. Your return is double your bet for heads and you lose your bet for tails. For example, if f?=?1/4, for the first toss you bet £0.25, and if heads comes up you win £0.5 and so then have £1.5. You then bet £0.375 and if the second toss is tails, you have £1.125. Choosing f to maximize your chances of having at least £1,000,000,000 after 1,000 flips, what is the chance that you become a billionaire? All computations are assumed to be exact (no rounding), but give your answer rounded to 12 digits behind the decimal point in the form 0.abcdefghijkl. This is problem 267. I'm looking forward to hearing your thoughts. Here is the solution : Answer: f=0.13, Probability is 0.999992836187 (I want to play this game :D ) // I've used C++ =========================================================== C++: #include<iostream.h> #include<math.h> double nCr(int n,int r) { double x=1;int ro; if(r > (n-r) ) { r=n-r; } for(int i=1, ro=r;i <=ro;n--,r--,i++) { x=x*( (double)n/r) *1; } return x; } double Cal(double f,int n,int flips) { double x; // n is the number of heads and ,(flips-n )is number of tails if(n>flips)return 0; x= pow(1+2*f,n)*pow(1-f,(flips-n)); return x; } //for a given fraction find the least number of heads for gains to be > than multipilcation //factor (10^9 in the problem) int leastn(double mulfactor,double fraction, int flips){ double fmax; int c=0; for(int i = 1 ; i<=flips; i++) { if(Cal(fraction,i,flips)>=mulfactor) return i; } return -1; } double binomail_Probability(int n, int flips) { double x=0; for(int i=n;i<= flips;i++){ x+= nCr(flips,i); } x=x/pow(2,flips); return x; } int main() { int n=0,i,flips; double f,bp=0,fg,na; double y,mf; cout<<"Enter the no of coin tosses:"; cin>>flips; cout<<"\nEnter the multiplication factor:"; cin>>mf; cout<<"\nPlease wait....\n"; for(f=0.01; f<=0.99; f+=0.001) { n=leastn(mf,f,flips); if(n>na) //if n is less hiher the probability { continue; } if(n==-1) continue; y=binomail_Probability(n,flips); //cout<<"f = "<<f<<" n = "<<n<<" p="<<y<<endl; if(y>bp) { fg=f; bp=y; na=n; } } cout<<"#######################\n"; cout.precision(12); if(bp!=0) cout<<"f = "<<fg<<" bp="<<bp<<"n is "<<na; else cout<<"Cannot generate so much returns with "<<flips<<" coin tosses...\n"; return 1; } PS: This code can be used by to find the probability and fraction f for any case Answer: f=0.13, Probability is 0.999992836187 #### Mr Doe Yep, the answer is correct . I'll give a brief explanation how I solved it. So, I start with a capital of 1, and each time my wealth is increased/decreased by: ((1+f\cdot X_k)), where ( X_k\sim { -1 ~~ 1\choose 1/2 ~~ 1/2 }), so after a 1000 flips my total wealth is (\prod_{k=1}^{1000}(1+f\cdot X_i)). My goal is to maximize the following quantity (\mathbb{P}(\prod_{k=1}^{1000}(1+f\cdot X_k)\geq 10^9)). First to check, that (10^9) is attainable, suppose I "win" each time, naturally I set (f=1) and I have (2^{1000}), and thats definitely greater than a billion. First we log the r.v. we are working with, and get (\sum_{k=1}^{1000}\operatorname{ln}(1+f\cdot X_k)), and we can easily see that this r.v. is a simple transformation of a binomial r.v., so we know how the get the prob. of the tail; (\mathbb{P}(\sum_{k=1}^{1000}\operatorname{ln}(1+f\cdot X_k)\geq 9\operatorname{ln}10)=\frac{1}{2^{1000}}\sum_{l=k_0(f)}^{1000}{1000\choose l}\rightarrow \operatorname{max}), so only the sum matters, and the sum is greater if (k_0(f)) is smaller. I subdivided the interval (\langle 0,1\rangle), and observed when I get the smallest (k_0(f)) (as a function of f), you should get a pretty picture like the one I attached. So, you find out that (f=0.13) is the one to go with (but you can choose f near the one that is mentioned as well, it wont matter), sum the binomial coefficients and you get the probability that pathfinder mentioned. It's a cool problem, but it has little to do with programming, I did all my work in Matlab (and it took me a couple of minutes), but just so I could get the pretty picture I attached. If anyone has another interesting problem related to probability/finance that involves a bit more programming skills please post it. usual #### Attachments • moja_slikica.jpg 15.7 KB · Views: 24 #### Andy Nguyen This is problem 50 in the project Eucler and an interesting one The prime 41, can be written as the sum of six consecutive primes: 41 = 2 + 3 + 5 + 7 + 11 + 13 This is the longest sum of consecutive primes that adds to a prime below one-hundred. The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953. Which prime, below one-million, can be written as the sum of the most consecutive primes? #### pathfinder This is problem 50 in the project Eucler and an interesting one The answer is 997651 which is the sum of 543 consecutive prime numbers from 7,11 to 3931 Here is the code in Perl C++: print "Enter the number(Example:1,000,000):"; chomp($max=<stdin><stdin>);
print "\n";
@pr=();
my $index; my$max_sum=0;
my $max_num=0; sub isPrime { my$n= shift;

if($n eq 3 or$n eq 2)
{
return 1;
}
if($n%6 ne 1 &&$n%6 ne 5)
{
return 0;
}

my $sq=sqrt ($n);
$sq =sprintf("%d",$sq);

for($i=2;$i<=$sq;$i++)
{
return 0,if($n%$i eq 0);
}
return 1;
}

sub findsequence{

my $n=shift; my$f=$#pr; if($n%2 eq 0){
my $f=($n-1);
}

my $sum=0; for(my$j=$f ;$j >($f-$n) ; $j--) {$sum+=$pr[$j];
}

for(my $i=$f;$i>= ($n-1) ; $i--) { if($i ne $f) {$sum=$sum+$pr[$i-$n+1]-$pr[$i+1];
}

if(($sum <$max) and isPrime($sum)) { if($n > $max_num) {$max_num=$n ;$max_sum=$sum;$index=$i-$n+1;
}
return ($sum); } } return 0; } sub findnumber { my$l=2;
my $h=$#pr, $mid; while(($h-1) > $l ) {$mid = ($h+$l )/2;
$mid =sprintf("%d",$mid);

if(!(findsequence($mid) or findsequence($mid+1) ) )
{
$h=$mid ;
}
else
{
$l=$mid;
}

}

return ($l); } print "\n\tFinding primes from 1 to$max\n";

foreach(2..$max){ my$n=$_; print "." ,if($n % 10000 eq 0) ;
print "\n",if($n%100000 eq 0); push @pr,$n ,if(isPrime($n)); } print "\n\tSearching ".($#pr+1)." primes....\n";

my $sm=findnumber(); print "\n$max_sum is the largest Prime number below $max which is the sum of$max_num consecutive primes ($pr[$index],$pr[$index+1],....,$pr[$index+\$max_num -1])\n";
</stdin></stdin>

#### IlyaKEightSix

The answer to problem 5 that I got:

232792560

The code (in C++)--had to change the < symbol into (less than) because it screwed the text up:

C++:
#include<iostream>

using namespace std;

int main()
{
bool divisible=false;
int bigInt=20;
cout (less thanx2) bigInt (less than x2) endl;
while(divisible==false)
{
divisible=true;
for(int i=1; i(less than)20; i++)
{
if(bigInt%i!=0)
{
divisible=false;
bigInt+=20;
break;
}
}
}
cout(less than x2)bigInt;
}

#### alain

##### Older and Wiser
you should post how to do it in R.

Replies
0
Views
245
Replies
3
Views
289
Replies
0
Views
551
Replies
4
Views
1K
Replies
0
Views
4K