My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
November 30th, 2011, 07:23 AM   #1
Newbie
 
Joined: Nov 2011

Posts: 1
Thanks: 0

Prime Numbers Sum Algorithm Question

Hello guys and girls i am writting for the first time in this forum.To my question->
We have a number which we know is a sum of prime numbers. Lets say the number is 64.
it can be represented as two sum :
2+3+5+7+11+13+23 = 64
or
2+3+5+7+11+17+19 = 64
My question is if there is a way to find the combinations of which prime numbers summed is the number.A little confusing...
In my example if we have 64 is there a way to find to find those 2 combinations listed and all possible ones for bigger numbers.
Again we know that the number is a sum of prime numbers we just need to find all combinations of which.And one more thing the prime numbers cannot be repeated this is very important. Thank you in advance.
kokozko is offline  
 
November 30th, 2011, 08:53 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Prime Numbers Sum Algorithm Question

This is a hard problem, since there may be a large number of ways. The problem can be solved by recursion:
Code:
ways(n,lim=n)=if(n<2||lim<2,return(n==0));my(s);forprime(p=2,min(n,lim),s+=ways(n-p,p-1));s;
ways(64)
This sequence is Sloane's A000586; see that page for a table of values up to 1000. My simple function is only practical for n up to a few hundred; memoization would make it faster.
CRGreathouse is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
algorithm, numbers, prime, question, sum



Search tags for this page
Click on a term to search for related topics.
Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
prime algorithm theory and paralells to pascall PerAA Number Theory 4 March 3rd, 2013 07:52 AM
prime fibonacci algorithm theory PerAA Number Theory 2 November 11th, 2012 06:34 AM
prime algorithm theory PerAA Number Theory 9 November 10th, 2012 05:35 AM
Most efficient trial division algorithm using prime forms? Sebastian Garth Number Theory 15 December 24th, 2011 01:33 PM
Question about prime numbers proglote Number Theory 26 April 16th, 2011 01:45 PM





Copyright © 2018 My Math Forum. All rights reserved.