 81 - 99 of 99 Posts

#### error10

·
Joined
·
13,477 Posts
Quote:
 Originally Posted by metala Why would you need to hold such a value?
Why would you multiply two numbers if you didn't intend to use the result?

#### rabidgnome229

·
Joined
·
5,282 Posts
Quote:
 Originally Posted by metala Why would you need to hold such a value?
No primitive datatype can hold that value. You need to create/use a third party BigInteger type class

#### metala

·
##### Registered
Joined
·
1,198 Posts
Quote:
 Originally Posted by rabidgnome229 No primitive datatype can hold that value. You need to create/use a third party BigInteger type class
I know that. Maybe this is the reason I use GMP library in solving the RSA challenge.

Quote:
 Originally Posted by error10 Why would you multiply two numbers if you didn't intend to use the result?
Why would you multiply two number in first time?
My question was more deeply nested. I wanted to know if he intend to do power modulo operation, which won't need more than 32bits type (depending on the arguments).
I even tried this:

m ^ e === c (mod n)
like that:

Code:

Code:
``````int c = 1;
for (int i=0;i<e;i++){
c = (c*m)%n;
}``````
And it seems to work, even though it's only experimentally proved, and probably/for sure takes more cycles, than some fast power-modulo algorithms.

#### rabidgnome229

·
Joined
·
5,282 Posts
Quote:
 Originally Posted by metala I know that. Maybe this is the reason I use GMP library in solving the RSA challenge.
Sorry - though you asked what would hold it

#### rabidgnome229

·
Joined
·
5,282 Posts
I learned python today so I did numbers two and three to get my hands dirty a bit. Can anybody verify the solutions?

Code:
Code:
``````#!/usr/bin/env python

import sys

def fib_even():
sum = 0
last = (0, 1)
curr = 0

while sum < 4000000 :
curr = last + last
if not (curr % 2) :
sum += curr
last = (last, curr)
else:
return sum-curr

def get_fact(fact, num):
if not num in fact :
fact[num] = num * get_fact(fact, num-1)
return fact[num]

def factorial_sum(limit):
fact = {0 : 1, 1 : 1, 2 : 2}
r = xrange(3, limit+1)

for n in r:
num = n
sum = get_fact(fact, n % 10)

while n / 10 != 0 :
n /= 10;
f = get_fact(fact, n % 10)
sum += f
else:
if sum == num :
print " ", num, " is a solution"

sum = fib_even()
print "The sum of all even fibonacci number such that the sum is less than 4,000,000 is", sum

if len(sys.argv) < 2 :
factorial_sum(1000000)
else :
factorial_sum(int(sys.argv))``````

#### LiquidForce

·
##### Registered
Joined
·
2,724 Posts
could i use whitespace for these

Im learning java in school but really only know the basics

#### rabidgnome229

·
Joined
·
5,282 Posts
Here is the circular primes in python

Code:
Code:
``````#!/usr/bin/env python

import sys

##### function definitions #####

def is_prime(p, n) :
for d in p :
if (n/d)*d == n :
return False
else :
return True

##### begin main #####

# parse command line arguments
if len(sys.argv) < 2 :
limit = 1000000
else :
limit = int(sys.argv)

# seed list of primes
p = 
r = xrange(3, limit+1)
solution = []

# generate all primes in range
for n in r :
if is_prime(p, n) :
p = p + [n]

# iterate through all primes
for n in p :
# convert to a list of digits
s = str(n)
r = xrange(1, len(s))
valid = True

# check all rotations of the prime
for i in r :
rs = s[i:len(l)] + s[0:i]
if not int(rs) in p :
valid = False
else :
if valid == True :
solution = solution + [n]

for s in solution :
print s``````

#### Manyak

·
Joined
·
11,951 Posts
Discussion Starter · ·
5 more puzzles have been added to the first post, and they should be a bit harder than the first set. Enjoy

#### error10

·
Joined
·
13,477 Posts
Backtracking Sudoku looks interesting, though it hardly seems efficient. I could probably solve it by hand before the computer finishes. I think I'll try something else if you don't mind.

#### Manyak

·
Joined
·
11,951 Posts
Discussion Starter · ·
Quote:
 Originally Posted by error10 Backtracking Sudoku looks interesting, though it hardly seems efficient. I could probably solve it by hand before the computer finishes. I think I'll try something else if you don't mind.
Sure thing, if its better then why not?

Though I'm not sure how much faster you can get it, a good backtracking algorithm can do it in under 1s. I'd still like to see what you come up with though

#### error10

·
Joined
·
13,477 Posts
Quote:
 Originally Posted by Manyak Sure thing, if its better then why not? Though I'm not sure how much faster you can get it, a good backtracking algorithm can do it in under 1s. I'd still like to see what you come up with though
Something that uses all 4 cores of my Q9550, probably.

#### Manyak

·
Joined
·
11,951 Posts
Discussion Starter · ·
Quote:
 Originally Posted by error10 Something that uses all 4 cores of my Q9550, probably.
lol ok yeah, there's always that

#### mentholmoose

·
##### Registered
Joined
·
1,125 Posts
Here's the roman numerals one, in PHP:

Code:

Code:
``````[CODE]
<?php

\$handle = fopen("roman.txt", "r");

fclose(\$handle);

\$numbers_array = explode("\
", \$numbers_file);

foreach(\$numbers_array as \$number) {

\$number = preg_replace("/[\
\
]/", "", \$number);

print(\$number . ": " . strlen(\$number) . " characters beforehand.\
");

\$old = strlen(\$number);

\$number = str_replace("IIIII", "V", \$number);

\$number = str_replace("IIII", "IV", \$number);

\$number = str_replace("VIV", "IX", \$number);

\$number = str_replace("VV", "X", \$number);

\$number = str_replace("XXXXX", "L", \$number);

\$number = str_replace("XXXX", "XL", \$number);

\$number = str_replace("LXL", "XC", \$number);

\$number = str_replace("LL", "C", \$number);

\$number = str_replace("CCCCC", "D", \$number);

\$number = str_replace("CCCC", "CD", \$number);

\$number = str_replace("DCD", "CM", \$number);

\$number = str_replace("DD", "M", \$number);

print(\$number . ": ". strlen(\$number) . " characters afterward.\
");

print("There were " . (\$old - strlen(\$number)) . " characters saved.\
\
");

}

?>``````
[/CODE]

It's verified working with the txt you provided. I think there are a couple of small cases where it won't, but none in your example file.

#### vaporvr6

·
##### Registered
Joined
·
51 Posts
i'm need a new challenge. anyone got something for me?

#### vaporvr6

·
##### Registered
Joined
·
51 Posts
sorry, just read the first post. one should note that not every sodoku has a solution. i suppose it's reasonable to assume that every puzzle a book would give you has one, however. else it wouldnt be any fun.

#### metala

·
##### Registered
Joined
·
1,198 Posts
Quote:
 Originally Posted by vaporvr6 i'm need a new challenge. anyone got something for me?
I have something for you.
"Elliptic curve cryptography"

* Generate keys
* Encode
* Decode

PS. I'm interested in it, but don't have the time to try. AFAIK this is one of the most secure asymmetric encryptions.

PS2. 112bit ECC has the security level of 2048bit RSA. (fixed)

#### arkheii

·
##### Registered
Joined
·
1,758 Posts
Anyone looking for a good challenge may want to google for ACM programming competition questions.

#### ToastedZergling

·
##### Registered
Joined
·
2 Posts
I have given the #10 Crackless Wall Puzzle using javascript, but I'm having a problem calculating the larger values. I can get up to W (18, 5) = 7958, but if I go much further up on the first parameter I get array out of bounds errors and other ugly messages. Does anyone think they could lend a spare set of eyes to see how I can improve this? I'm thinking I will have to modify the permute function, which I didn't write to begin with

=( Sad face at modifying other people's code, I like it when their work can just be a big black box.

#### ToastedZergling

·
##### Registered
Joined
·
2 Posts
I've moved on from this problem and into another! So if anyone wants to help me out / check out my progress thus far take a look here. It's all about optimization at this point.

Quote:
 Originally Posted by ToastedZergling I have given the #10 Crackless Wall Puzzle using javascript, but I'm having a problem calculating the larger values. I can get up to W (18, 5) = 7958, but if I go much further up on the first parameter I get array out of bounds errors and other ugly messages. Does anyone think they could lend a spare set of eyes to see how I can improve this? I'm thinking I will have to modify the permute function, which I didn't write to begin with =( Sad face at modifying other people's code, I like it when their work can just be a big black box.

81 - 99 of 99 Posts