Numbers easy to factor

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Numbers easy to factor

Postby Goahead52 » Tue Dec 30, 2014 2:47 pm UTC

All those numbers are easy to factor using a pen and paper

109223
76633
31309
85769
196241
66277
181367
26269
116267
197503
170999
47263
40727
135229
72299
125249
177311
152021
130381
93473
65567
163201
78937
101911
184507
147443
45803
122237
100127
70723
107413
24503
53111
168319
149647
172253
165923
91829
116393
146747
137297
30397
40619
171463
47867
170909
37391
34387
46357
96427

There are an infinite odd numbers like those above.
Do you know other odd composite numbers (except those detected with known rules of divisibility) easy to be factored?

Thank you

User avatar
Forest Goose
Posts: 377
Joined: Sat May 18, 2013 9:27 am UTC

Re: Numbers easy to factor

Postby Forest Goose » Tue Dec 30, 2014 5:02 pm UTC

Define "easy to factor" for an integer independent a method.

I mean this with as little offense as possible, and maybe this is a language thing, but I feel like your posts are hinting at an idea you have rather than showing and explaining what you are actually thinking. Like a riddle leading up to it - again, that may just be my impression. At any rate, you seem like you have more to say than that those numbers are simple to factor, like you have some notion in mind. Is that accurate? If so, what? If not, then please answer the first question above.

:-)
Forest Goose: A rare, but wily, form of goose; best known for dropping on unsuspecting hikers, from trees, to steal sweets.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Numbers easy to factor

Postby Goahead52 » Tue Dec 30, 2014 5:38 pm UTC

Easy to factor is easy to define.
Let start from the rule of divisibity by 2.
An even number id divisible by 2.
By 3 you count the sum of the digits and if the sum is divisible by 3 then the number no matter how big is will be divisible by 3.
You find the 2 facotors 2 and 3 easily.
The same process lead after a quick test (pen and paper not more than 10 minutes) to the fact that those numbers above and others are composite first and easy to factorize because you know how to find them by direct formula.
My idea is the process of multiplication in many cases is easy to reverse.
It is like reenginieering the process.
All the odd numbers are in fact families of numbers.
As they are infinite we will surely find an infinite number of families.
However if we find families of solutions such as we cover (20% of all odd numbers at least up to say 10000 digits) we could break with 1 chance out of 5 some big semiprime numbers.
That is my goal.
If you break with those methods ONE RSA number (not more) all the business built around the difficulty of factorizing will be broken and worth zero.
I suspect those providing those semiprime numbers of giving numbers easy to retrieve. Numbers belonging to some complex family.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Numbers easy to factor

Postby Goahead52 » Tue Dec 30, 2014 5:40 pm UTC

Those numbers above are easy to factorize : they are based on triangular numbers. I say : based! not the triangular numbers themselves.

User avatar
Forest Goose
Posts: 377
Joined: Sat May 18, 2013 9:27 am UTC

Re: Numbers easy to factor

Postby Forest Goose » Tue Dec 30, 2014 5:49 pm UTC

I'm not sure I understand.

Knowing the formula ahead of time makes it easy, sure, but with a lack of formulas, what do you do? Ir, are you proposing some sort of test formulas to try against a given number? That you can dream up formulas, then easily factor the results does not entail anything about how hard factorization is - I'm not really seeing any method that falls out of anything you are saying, could you be more specific?
Forest Goose: A rare, but wily, form of goose; best known for dropping on unsuspecting hikers, from trees, to steal sweets.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Numbers easy to factor

Postby Goahead52 » Tue Dec 30, 2014 7:04 pm UTC

For example this 11 digits number :

70374763783 = 187277 * 375779

You could easily factorize it using pen and paper in less than 10 minutes.
Why?
Because it belongs to a family of numbers having some form.
By building odd numbers and classifying them in families it will be easy to factorize them.
You have to build a quick test to know if this number belong to the X family and if yes.
You can factorize it in seconds.
The hard problem in fact is to find the best covering for each family.
Here n=70374....783
You compute A=2*n=k^2+r where k^2 is the biggest square < A
You compute d=k-r and if d is of the s(s+1) then the number is composite and could be factorized easily.

User avatar
Forest Goose
Posts: 377
Joined: Sat May 18, 2013 9:27 am UTC

Re: Numbers easy to factor

Postby Forest Goose » Tue Dec 30, 2014 7:45 pm UTC

That everything has a form doesn't translate into everything has a form the is useful for factoring and easily checked -- and that we can cover the naturals with a set whose growth rate is small. It's like saying "Every nontrivial 0 of the zeta function has a form, we just need to show those forms are all on the critical strip" or "To win the race, you just need a more aerodynamic car with a more powerful engine that weighs less and handles better", unless you have something quite strong to put up beside that to make your point, you really haven't even left the gate.

I'm not saying don't try this, or trying to be discouraging, but your observation doesn't go anywhere by itself. Do you have some such solution covering in mind? Or something that may lead to one, in general? It's fun to fantasize about breaking RSA, and all that, but unless you've got something a lot more powerful motivating this, I would say it is highly unlikely it will get there.
Forest Goose: A rare, but wily, form of goose; best known for dropping on unsuspecting hikers, from trees, to steal sweets.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Numbers easy to factor

Postby Goahead52 » Tue Dec 30, 2014 9:02 pm UTC

It is like going to Formula 1 race with a donkey.
Thank you for your advise.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Numbers easy to factor

Postby Goahead52 » Tue Dec 30, 2014 9:04 pm UTC

Sometimes one`s have to be little bit crazy.

User avatar
Forest Goose
Posts: 377
Joined: Sat May 18, 2013 9:27 am UTC

Re: Numbers easy to factor

Postby Forest Goose » Wed Dec 31, 2014 4:35 am UTC

Goahead52 wrote:It is like going to Formula 1 race with a donkey.


If that is so, then math, at this point in the game, is not a Formula 1 race, but a "bring your weird ride" race.

But, at any rate, I'm not telling you not to try radical new things, or not to pursue ideas, but to clarify your idea and make sure you have one to pursue. In other words - bring a donkey to the race, if you will, but make sure you are actually at the races, not on a merry-go-round.

See, here's the thing, "Covering the naturals" isn't really an idea, it's more a direction to go in, an observation, and the methods you list are, essentially, a few neat observations. What you have doesn't, won't, can't, etc. just blossom into a solution of the type you are considering - thus, you need something that actually gets the job done, something to build on, that's what I'm trying to ask: what is that thing?

Math is a lot like writing a novel, everyone thinks it is about coming up with this neat idea for a story, something fresh, and, then, it's just a matter of writing it. But, really, neat story ideas are a dime a dozen, it's refining that down into actual words on a page, words that actually work, that is the difficult part. What I'm seeing here is a neat story idea and a title for the book, I'm not seeing words on a page - I'm trying to suggest that you write those words.
Forest Goose: A rare, but wily, form of goose; best known for dropping on unsuspecting hikers, from trees, to steal sweets.

Cradarc
Posts: 455
Joined: Fri Nov 28, 2014 11:30 pm UTC

Re: Numbers easy to factor

Postby Cradarc » Wed Dec 31, 2014 5:56 am UTC

I'm not sure what family you are creating with your eleven digit number. However, the shortcuts for division by numbers like 2, 4, 3, 11, etc. are based on modulo arithmetic.

10^n = 1 mod 3, for all n.
Since every integer can be expressed as n = a0 + 10a1 + 100a3 + ...
Under modulo 3 that's equivalent to a0 + a1 + a2 + ...
The reason you can work in modulo 3 in the first place is because you want to figure out if the number is divisible by 3. Modulo 3, by definition ignores anything that is divisible by 3. In this case, modulo 3 happen to simplify the powers of 10 nicely.

Consider a larger number like 17:
(the following is all modulo 17)
10 = 10
100 = 15
1000 = 150 = 65 = 14
10000 = 140 = 55 = 7
There's no obvious pattern. You will need to store 16 different values to hold all the data for this single prime.

Because there are an infinite number of primes, you won't be able to get a finite "family" of numbers. As the numbers you are working with get larger, you will need to check more and more families. Unless you somehow cracked the secret to prime numbers, you won't be able to identify the divisibility of a large number without performing checks equal to the number of primes less than its square root*.

*Currently this limit is bypassed by performing guesses and heuristic tests rather than straight out attacking the number itself.
This is a block of text that can be added to posts you make. There is a 300 character limit.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Numbers easy to factor

Postby Goahead52 » Wed Dec 31, 2014 3:41 pm UTC

Here is the example of n=109223
How do I know that this number is quickly to be factored?
I compute n=t(k)+r where t(k) is a triangular number (k(k+1))/2
n=t(466)+412
I compute k-r=466-412=54
I check if 54+1 is equal to some triangular number
55+1=55=(10*11)/2=t(10)
It is!!!!
Then n=109223 is 100% composite!!!!
If you understand that then you could find easily how to factor it.
Factoring it is elementary so I will let you find it.

We could build 1000 of families of solutions using only elementary tools.
My project goes in that direction but what I want to find is few families covering the maximum number of odd composites (above all those with 2 factors of the same size).
I think that it is doable. It requires a team and I work alone.

schapel
Posts: 244
Joined: Fri Jun 13, 2014 1:33 am UTC

Re: Numbers easy to factor

Postby schapel » Wed Dec 31, 2014 5:10 pm UTC

Goahead52 wrote:For example this 11 digits number :

70374763783 = 187277 * 375779

You could easily factorize it using pen and paper in less than 10 minutes.
Why?
Because it belongs to a family of numbers having some form.

I suppose I could say that many multiples of 75743258729 are easy to factor using pen (why not pencil?) and paper. They all belong to a family of numbers having some form. The thing is, you need to know that the number you're factoring is a multiple of 75743258729 before you've factored it. That makes my claim far less impressive.

Here's another family that's easy to factor: Tenth powers. All you need to do is raise the number to the 0.1 power and see if it's an integer.

BTW, I just randomly typed the 11 digits above and just happened to come up with a prime on the first try! What are the odds?

User avatar
Sizik
Posts: 1222
Joined: Wed Aug 27, 2008 3:48 am UTC

Re: Numbers easy to factor

Postby Sizik » Wed Dec 31, 2014 5:34 pm UTC

schapel wrote:BTW, I just randomly typed the 11 digits above and just happened to come up with a prime on the first try! What are the odds?


Just under 4%
gmalivuk wrote:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.

curiosityspoon
Posts: 35
Joined: Wed Sep 24, 2014 5:01 pm UTC

Re: Numbers easy to factor

Postby curiosityspoon » Wed Dec 31, 2014 5:41 pm UTC

Goahead52 wrote:Here is the example of n=109223
How do I know that this number is quickly to be factored?
I compute n=t(k)+r where t(k) is a triangular number (k(k+1))/2
n=t(466)+412
I compute k-r=466-412=54
I check if 54+1 is equal to some triangular number
55+1=55=(10*11)/2=t(10)
It is!!!!
Then n=109223 is 100% composite!!!!
If you understand that then you could find easily how to factor it.
Factoring it is elementary so I will let you find it.

We could build 1000 of families of solutions using only elementary tools.
My project goes in that direction but what I want to find is few families covering the maximum number of odd composites (above all those with 2 factors of the same size).
I think that it is doable. It requires a team and I work alone.


Let's try the example n=6,700,417:
I choose k=-3,350,209, leading to the triangular number t(k)=5,611,951,846,945, so r=-5,611,948,496,736.

I compute k-r=5,611,945,146,527.

I check if 5,611,945,146,527+1 is equal to some triangular number.
5,611,945,146,528=(3,350,207*3,350,208)/2=t(3,350,207)

It is! So 6,700,417 must be 100% composite...right?

(Of course, if you try to apply the factoring transformation on these k-values, you end up finding factors of 1 and 6,700,417, which is in fact the best you can do.)

Also, rather than finding k and r such that t(k)+r=n, you can try moving the k value one higher, so that you then look for t(k)-r=n. Then you just check if r is a triangular number directly, instead of having the further step of taking k-r and adding 1 to it. This gives rise to a construction with an obligatory Wikipedia reference.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Numbers easy to factor

Postby Goahead52 » Wed Dec 31, 2014 6:15 pm UTC

I tried n=6700417
n is not composite
k=3660
r=787
k-r=2873
2874 is not a triangular number
hence n is not composite.

curiosityspoon
Posts: 35
Joined: Wed Sep 24, 2014 5:01 pm UTC

Re: Numbers easy to factor

Postby curiosityspoon » Wed Dec 31, 2014 6:42 pm UTC

Because you're not choosing the right k value, of course! Just like if you try it with n=291: if you choose k=23, t(k)=276, r=15, but 23-15+1 = 9 is not triangular. Does that mean it's not composite? Well, if you try again with k=50, t(k)=1275, r=-984, then this time k-r+1 = 1035 will lead you to finding 45*46/2 = 1035 = t(45), and the correct factorization 3*97. You can also get it to work with k=97, k=-53, or k=-100.

Now see what happens when you try again with the proper choice of k=-3,350,209 (or k=+3,350,208 if you'd rather not use negative values).
Last edited by curiosityspoon on Wed Dec 31, 2014 6:50 pm UTC, edited 1 time in total.

brenok
Needs Directions
Posts: 507
Joined: Mon Oct 17, 2011 5:35 pm UTC
Location: Brazil

Re: Numbers easy to factor

Postby brenok » Wed Dec 31, 2014 6:45 pm UTC

How are you choosing the value of k?

curiosityspoon
Posts: 35
Joined: Wed Sep 24, 2014 5:01 pm UTC

Re: Numbers easy to factor

Postby curiosityspoon » Wed Dec 31, 2014 6:55 pm UTC

That's the thing: you have to find a value that will work out of all the possible candidates, which devolves into factoring the number to begin with! Choosing k to create the largest possible triangular number that doesn't exceed the number to be tested (or, in the alternative formulation, the smallest triangular number that does) will only succeed in certain cases where one of the prime factors is roughly twice the other one, but there are k values that will purportedly crack any number whatsoever, except for powers of 2. Once again, the article on trapezoidal numbers is relevant.
Last edited by curiosityspoon on Wed Dec 31, 2014 6:55 pm UTC, edited 1 time in total.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Numbers easy to factor

Postby Goahead52 » Wed Dec 31, 2014 6:55 pm UTC

curiosityspoon wrote:Because you're not choosing the right k value, of course! Just like if you try it with n=291: if you choose k=23, t(k)=276, r=15, but 23-15+1 = 9 is not triangular. Does that mean it's not composite? Well, if you try again with k=50, t(k)=1275, r=-984, then this time k-r+1 = 1035 will lead you to finding 45*46/2 = 1035 = t(45), and the correct factorization 3*97. You can also get it to work with k=97, k=-53, or k=-100.

Now see what happens when you try again with the proper choice of k=-3,350,209 (or k=+3,350,208 if you'd rather not use negative values).


t(k) is the biggest triangular number < n
It is obvious.
Why not choosing k > n ?

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Numbers easy to factor

Postby Goahead52 » Wed Dec 31, 2014 6:57 pm UTC

You can test it if you want.
It works!

Cradarc
Posts: 455
Joined: Fri Nov 28, 2014 11:30 pm UTC

Re: Numbers easy to factor

Postby Cradarc » Wed Dec 31, 2014 9:52 pm UTC

Okay, I think I know what you're talking about now.

Given:
k - r + 1 = s(s+1)/2
r < k+1 = (k+1)(k+2)/2 - k(k+1)/2

Your claim is for any integer k, r, s, that satisfies the above three statements, n = k(k+1)/2 + r must be composite.
(The first statement is your test. The second statement is saying k(k+1)/2 is the largest triangle number smaller than n.)

Rearranging first statement:
r = k+1 - s(s+1)/2
For all s,k > 0, the second statement is now guaranteed to be true.

Substitute it into the expression for n:
n = k(k+1)/2 + k+1 - s(s+1)/2
n = (k+1)(k+2)/2 - s(s+1)/2

For any positive k > s, we show T(k+1)-T(s) is composite:
T(k+1)-T(s) can be expressed as a finite series of consecutive integers from s+1 to k+1. This is because the jth triangle number corresponds to the sum of consecutive positive integers up to j.
(s+1) + (s+2) + (s+3) + ... +(k+1) = (k+s+2)(k-s+1)/2
So (k+s+2) or (k+1-s) must be a factor of n.

Your approach is to generate a large table of triangle numbers (essentially consecutive sums). Then perform the following:

Code: Select all

int k = 1;
While (T(k) < n)
 k++;
end
k--;
int r = n-T(k-1);
int s == T.getIndex(r);

if(s != -1)
 if((k+s)%2 == 1)
  return (k+s+2);
 end
 return (k-s+1);
else
//This is the part where you will have problems
end


What happens if r turns out not to be a triangle number? The number could still be composite, and you're stuck.
Remember your r can vary between 1 and k+1. k will have approximately half the bits of n. Furthermore, triangle numbers become more and more sparsely distributed as the size of the numbers increase. You will need a way to make good guesses for k instead of always picking the largest value.
This is a block of text that can be added to posts you make. There is a 300 character limit.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Numbers easy to factor

Postby Goahead52 » Wed Dec 31, 2014 10:04 pm UTC

Thank you for all the clarification.
I will check out your post later.
What is really interesting in the case of this family of numbers :
1. Counting function of those numbers less than N is easy and precise.
2. Finding those numbers is easy. No need for guessing or whatsoever.

I wish you all happy new year from Canada.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Numbers easy to factor

Postby Goahead52 » Thu Jan 01, 2015 4:18 pm UTC

What if r is not a triangular number?
Nothing will happen.
Am I missing something?

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Numbers easy to factor

Postby Goahead52 » Thu Jan 01, 2015 6:55 pm UTC

More interesting here is that if n does not belong to this family it ALWAYS exists a multiple of n of the form n*m belonging to this family and consequently easily factored.
How to find the m without knowing the factorization of n?
Big question!
If you could answer to that question then you could factorize any odd composite number.
That is the challenge of 2015!!!
Someone will surely win it. Not me for sure.

Cradarc
Posts: 455
Joined: Fri Nov 28, 2014 11:30 pm UTC

Re: Numbers easy to factor

Postby Cradarc » Thu Jan 01, 2015 8:07 pm UTC

Goahead52 wrote:What if r is not a triangular number?
Nothing will happen.
Am I missing something?


You just went through a nontrivial amount of computation and gained no useful information (if r is not triangle). It's not such a big deal if you're working stuff out by hand, but for a computer, every little bit counts.

Goahead52 wrote:More interesting here is that if n does not belong to this family it ALWAYS exists a multiple of n of the form n*m belonging to this family and consequently easily factored.


Suppose you find nm that can be factored using the method. You end up finding the two factors n and m. n is still not factored.
For example:
Let's say n and m are both odd. We need to find k,s so that (k+s+2) = n and (k-s+1)/2 = m
k+s = n-2
k-s = 2m-1
k = 0.5(2m+n-3)
s = n-2-k

Now y = (k+s+2)(k-s+1)/2 is a number of the form nm that can be factored using your method. However you still don't know what are the factors of n.
This is a block of text that can be added to posts you make. There is a 300 character limit.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Numbers easy to factor

Postby Goahead52 » Thu Jan 01, 2015 8:31 pm UTC

Cradarc wrote:
Goahead52 wrote:What if r is not a triangular number?
Nothing will happen.
Am I missing something?


You just went through a nontrivial amount of computation and gained no useful information (if r is not triangle). It's not such a big deal if you're working stuff out by hand, but for a computer, every little bit counts.

Goahead52 wrote:More interesting here is that if n does not belong to this family it ALWAYS exists a multiple of n of the form n*m belonging to this family and consequently easily factored.


Suppose you find nm that can be factored using the method. You end up finding the two factors n and m. n is still not factored.
For example:
Let's say n and m are both odd. We need to find k,s so that (k+s+2) = n and (k-s+1)/2 = m
k+s = n-2
k-s = 2m-1
k = 0.5(2m+n-3)
s = n-2-k

Now y = (k+s+2)(k-s+1)/2 is a number of the form nm that can be factored using your method. However you still don't know what are the factors of n.

Thank for all the clarification.
You choose the worst case.
Now just try m={2,3,4....t}
Try them consecutively and you will find lot of numbers giving one of the factors of n.
I tested it.
Use the computer and your program.
Once you do it then try to explain why?
I`m sure you will find the solution : choosing the m who will solve your factorization.
Do not start from m and n as you did.
Try n*m with m varying from 2 to t (t bigger as you wish).
The way to find the "good m" factoring n need some use of pencil and paper.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Numbers easy to factor

Postby Goahead52 » Thu Jan 01, 2015 9:55 pm UTC

Let us take n=123
n is not of the family "easy to be factored" family based on triangular numbers.
Let us change it into member by multiplying n by m=5

n*m=615
k=34
r=20
k-r=14
14+1=15=t(5)

hence 615 now belong to the family

615 is divided by k+s+2=34+5+2=41
123 is divisible by 41 too

We have then factorized n

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Numbers easy to factor

Postby Goahead52 » Thu Jan 01, 2015 9:56 pm UTC

How to find m?
Billion dollar question :D :D :D

brenok
Needs Directions
Posts: 507
Joined: Mon Oct 17, 2011 5:35 pm UTC
Location: Brazil

Re: Numbers easy to factor

Postby brenok » Thu Jan 01, 2015 10:44 pm UTC

Or you could notice that 123 is divisible by 3...

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Numbers easy to factor

Postby Goahead52 » Thu Jan 01, 2015 10:53 pm UTC

brenok wrote:Or you could notice that 123 is divisible by 3...

Right!
But it was just an example to show how it works.
I could give an example with some n not divisible even by the first 10000 primes.
It will take time for checking and so on.
Now please read all the posts then if something is really wrong then do not hesitate to signal it.
Thank you.

Cradarc
Posts: 455
Joined: Fri Nov 28, 2014 11:30 pm UTC

Re: Numbers easy to factor

Postby Cradarc » Fri Jan 02, 2015 1:36 am UTC

It's the billion dollar question, because it's the same problem as factoring n!

Let mn = (k+s+2)(k-s+1)/2
Let (k+s+2) = p, (k-s+1)/2 = q
Notice p and q can be any odd integers. (See how I solved for k,s in terms of n,m in previous post. replace n,m with p,q, and you have the proof).
So what do we have now?
m = pq/n, where p and q can be any odd integers, and m has to be an integer.
You want solutions for m where neither p nor q is divisible by n. You can't figure that out without factoring n in some way or another.

Think of it this way: Every time you pick an m, you are actually picking a k,s pair (where k,s is not always an integer). This is because any particular mn will generate a unique k,s pair. So once m is fixed, p and q are fixed.
The question is essentially "How do we determine p,q so that pq/n is an integer but neither p/n nor q/n are integers?"
That is as difficult as asking for two nontrivial factors of n.
This is a block of text that can be added to posts you make. There is a 300 character limit.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Numbers easy to factor

Postby Goahead52 » Fri Jan 02, 2015 11:22 am UTC

Cradarc wrote:It's the billion dollar question, because it's the same problem as factoring n!

Let mn = (k+s+2)(k-s+1)/2
Let (k+s+2) = p, (k-s+1)/2 = q
Notice p and q can be any odd integers. (See how I solved for k,s in terms of n,m in previous post. replace n,m with p,q, and you have the proof).
So what do we have now?
m = pq/n, where p and q can be any odd integers, and m has to be an integer.
You want solutions for m where neither p nor q is divisible by n. You can't figure that out without factoring n in some way or another.

Think of it this way: Every time you pick an m, you are actually picking a k,s pair (where k,s is not always an integer). This is because any particular mn will generate a unique k,s pair. So once m is fixed, p and q are fixed.
The question is essentially "How do we determine p,q so that pq/n is an integer but neither p/n nor q/n are integers?"
That is as difficult as asking for two nontrivial factors of n.

There are an infinite values of m giving the factorization.
Check for n=615 m={5,6,7,8,....} so why are thinking that m will generate unique pair of k and s ? and even if it generate a unique (k,s) the aim is to isolate ONE FACTOR not both.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Numbers easy to factor

Postby Goahead52 » Fri Jan 02, 2015 11:35 am UTC

91
273
455
546
819
910
1092
1274
1638
1820
2275
2457
2730
3003

n=7*13=91
All the multiples of 91 listed above belong to the same familiy and are easy to be factored.
The list is infinite in fact.
If there exist an infinite number of m`s all we need is to find only one FACTOR of n to solve the problem.
We do not need the factorization of n to find m.
m could be found otherwise.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Numbers easy to factor

Postby Goahead52 » Fri Jan 02, 2015 12:03 pm UTC

Here is my solution :

We start by testing if n belong to one of 2 families.
Family 1 : based on (k,r) or (k,-r) (see here http://forum.projecteuler.net/viewtopic.php?f=17&t=3737 )
Family 2 : based on triangular numbers (see the post above)

n does not belong to any of the 2 families.
Hence we have to find m such as m*n makes that number belonging to the 2 families.
Assuming that there exist a number m leading n to belong to the 2 families we will have an equation system with 2 equations and 2 unknowns (m and s).
We will not need then to know the factorization of n to find m.
I hope it will work.
We have to keep in mind that there are links between the 2 s`s.
How to formulate all this and fix some problems needs time?

546=91*6 for example belong to the 2 families with m=6 for n=91=7*13

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Numbers easy to factor

Postby Goahead52 » Fri Jan 02, 2015 12:45 pm UTC

n here must be taken as n=pq or as generic N=m*n (multiple of n).
You have chosen one case n=pq so that is maybe where you are wrong.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Numbers easy to factor

Postby Goahead52 » Fri Jan 02, 2015 3:31 pm UTC

Thank you and good luck to all those who contributed.
I finished my job by finding definitely the solution.

User avatar
Lopsidation
Posts: 183
Joined: Tue Oct 27, 2009 11:29 pm UTC

Re: Numbers easy to factor

Postby Lopsidation » Fri Jan 02, 2015 4:42 pm UTC

You may want to look up the quadratic sieve, it has a similar idea to what you propose but with square numbers instead of triangular numbers. It's quite fast.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Numbers easy to factor

Postby Goahead52 » Fri Jan 02, 2015 9:55 pm UTC

Lopsidation wrote:You may want to look up the quadratic sieve, it has a similar idea to what you propose but with square numbers instead of triangular numbers. It's quite fast.

I know the quadratic sieve and I do not need it.
The solution is tricky one.
You have to write n as function of 3 integers m,x,y minimizing y and finding m and x such as n*m become a member of family (easily factored).
You do not NEED to know the factorization of n.

Ps : Please I`m the guy who do not care about what was done (I read many algorithms and I have an idea about them).
Mathematical solution are essentialy ideas first then technicalities after.
You can not create something new if you stick to what was done.
You have to reread the history of the mathematics to know it. Any approach enslaved by centuries of research is doomed to fail (almost 100%).
Continuity is rare when it comes to solving problems.

Cradarc
Posts: 455
Joined: Fri Nov 28, 2014 11:30 pm UTC

Re: Numbers easy to factor

Postby Cradarc » Fri Jan 02, 2015 9:55 pm UTC

Goahead52 wrote:There are an infinite values of m giving the factorization.
Check for n=615 m={5,6,7,8,....} so why are thinking that m will generate unique pair of k and s ? and even if it generate a unique (k,s) the aim is to isolate ONE FACTOR not both.


1. Each m generates unique k,s because a given mn will generate a unique k,s.

2. p,q are any odd integers, because mn = (k+s+2)(k-s+1)/2 = pq. If either p or q is even, then let m = (m/2) and you will get a solution for m that have p,q odd. This is assuming n is odd.
I guess you can define p = (k+s+2)/2 and q = (k-s+1), but it wouldn't change the results due to symmetry.

3. Yes there are infinite m that give the factorization. However finding the correct m is as hard as guessing the correct k, while keeping m fixed.

Assume you find an m that gives you a factorization of n:
m = qp/n
q is a nontrivial factor of n, so obviously q/n is not an integer. (you can swap q with p and it the argument still holds)
p must divide (n/q) in order for m to be an integer.
p = j(n/q), j = any integer
Now consider m/j = qp/(nj) = q(n/q)/n = 1.

So you instead of multiplying by m, you can just allow k to vary instead of fixing it as the maximum value. You're essentially looking for any integers k,s such that:
n = (k+s+2)(k-s+1)/2

Cradarc wrote:You will need a way to make good guesses for k instead of always picking the largest value.

You have rephrased the problem, but the difficulty is still there.
This is a block of text that can be added to posts you make. There is a 300 character limit.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 11 guests