Overclock.net banner
81 - 99 of 99 Posts

·
Premium Member
Joined
·
13,477 Posts
Quote:

Originally Posted by metala View Post
Why would you need to hold such a value?
Why would you multiply two numbers if you didn't intend to use the result?
 

·
Premium Member
Joined
·
5,282 Posts
Quote:

Originally Posted by metala View Post
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
 

·
Registered
Joined
·
1,198 Posts
Quote:

Originally Posted by rabidgnome229 View Post
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 View Post
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.
 

·
Premium Member
Joined
·
5,282 Posts
Quote:


Originally Posted by metala
View Post

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
 

·
Premium Member
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[0] + last[1]
if not (curr % 2) :
sum += curr
last = (last[1], 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[1]))
 

·
Premium Member
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[1])

# seed list of primes
p = [2]
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
 

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

·
Premium Member
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.
 

·
Premium Member
Joined
·
11,951 Posts
Discussion Starter · #90 ·
Quote:


Originally Posted by error10
View Post

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
 

·
Premium Member
Joined
·
13,477 Posts
Quote:

Originally Posted by Manyak View Post
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.
 

·
Premium Member
Joined
·
11,951 Posts
Discussion Starter · #92 ·
Quote:

Originally Posted by error10 View Post
Something that uses all 4 cores of my Q9550, probably.

lol ok yeah, there's always that
 

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

Code:

Code:
[CODE]
<?php

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

$numbers_file = fread($handle, filesize("roman.txt"));

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.
 

·
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.
 

·
Registered
Joined
·
1,198 Posts
Quote:


Originally Posted by vaporvr6
View Post

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)
 

·
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.
 

·
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 View Post
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
Top