p | f(m,n)
 

There is this function f(m,n), where:

p | m & p | n => p^2 | f(m,n)

p !| m & p | n => p !| f(m,n)

p | m & p !| n => p | f(m,n)

p !| m & p !| n => p !| f(m,n)

For integers m, n and p

I have an intuitive feeling that there is a theoretical factoring significance to this function. But I can't formulate anything useful out of it.

Thank you in advance for any comments/inputs.:smile:

[QUOTE=a1call;462855]There is this function f(m,n), where:

p | m & p | n => p^2 | f(m,n)

p !| m & p | n => p !| f(m,n)

p | m & p !| n => p | f(m,n)

p !| m & p !| n => p !| f(m,n)

For integers m, n and p[/QUOTE]

p can be any integer, not just a prime?

[QUOTE=a1call;462855]I have an intuitive feeling that there is a theoretical factoring significance to this function. But I can't formulate anything useful out of it.[/QUOTE]

Me either.

[QUOTE=a1call;462855]There is this function f(m,n), where:

p | m & p | n => p^2 | f(m,n)

p !| m & p | n => p !| f(m,n)

p | m & p !| n => p | f(m,n)

p !| m & p !| n => p !| f(m,n)

For integers m, n and p

I have an intuitive feeling that there is a theoretical factoring significance to this function. But I can't formulate anything useful out of it.

Thank you in advance for any comments/inputs.:smile:[/QUOTE]

The second one, doesn't hold for a straight product mn, being the output of the function ( assuming !| is does not divide).

Thank you for the reply SM.
The function is not a product. And that's the significant of the function that it only is divisible by factor of n if n is also divisible by that factor. And m and n are not interchangeable.

[QUOTE=CRGreathouse;462875]p can be any integer, not just a prime?



Me either.[/QUOTE]

Yes p can be any integer. The function does not have a practical value as is, because it is exponential and yields very large integers. But I think the concept of a function having non interchangeable inputs has theoretical use in factoring size notwithstanding.

[QUOTE=a1call;462855]There is this function f(m,n), where:

p | m & p | n => p^2 | f(m,n)

p !| m & p | n => p !| f(m,n)

p | m & p !| n => p | f(m,n)

p !| m & p !| n => p !| f(m,n)

For integers m, n and p[/QUOTE]

Let m = 2 and n = 4. Then 4 | f(m,n) since 2 | m and 2 | n. But also 4 !| f(m,n) since 4 !| m and 4 | n. So there is no such function.

If you intended for p to be restricted to primes rather than integers as you wrote, then you can just use f(m, n) = m^2.

[QUOTE=a1call;462855]There is this function f(m,n), where:

p | m & p | n => p^2 | f(m,n)

p !| m & p | n => p !| f(m,n)

p | m & p !| n => p | f(m,n)

p !| m & p !| n => p !| f(m,n)

[/QUOTE]

The problems with this, as CRG's example points out, is that some of these combined are true only over certain subsets of integers.

the first is true as long as [TEX]\left|\frac{m}{p}\right| \& \left|\frac{n}{p}\right|[/TEX] are both integer. ( in this case m=p=n is possible, as well as them being any positive powers of each other etc. ordering doesn't really matter for m and n in this one to be true, as long long as p divides into the minimum of them.)

the second and third ones only care if one ( though a specific one) of those is integer (m can't be a positive power of n in the second, n can't be a positive power of m in the third, p could be a positive power of m in the second, or a positive power of n in the third) .

the fourth is there for when neither of that set are integer. ( both m,n can't be positive powers of p, p can be any integer whose absolute value isn't a divisor of m or n).

[QUOTE=CRGreathouse;462897]Let m = 2 and n = 4. Then 4 | f(m,n) since 2 | m and 2 | n. But also 4 !| f(m,n) since 4 !| m and 4 | n. So there is no such function.

If you intended for p to be restricted to primes rather than integers as you wrote, then you can just use f(m, n) = m^2.[/QUOTE]




All my reply was wrong so I deleted it pending further figuring out.

[QUOTE=a1call;462925]All my reply was wrong so I deleted it pending further figuring out.[/QUOTE]

The fourth, also doesn't work for a general difference or a sum of m and n, because 6-1=5 and 6+1=7 which are divisible by 5 and 7 but 6 doesn't divide by either and neither does 1. Also, if m and n are opposite class mod p, then their sum is a multiple of p. If they are the same class, then their difference is a multiple of p.

The truth table I gave in OP is false. Please disregard it.

Here are some actual results:

------------------------
m=7;n=11;
valuation(f(m,n),5)=0
------------------------
m=5;n=11;
valuation(f(m,n),5)=1
------------------------
m=7;n=5;
valuation(f(m,n),5)=0
------------------------
m=5;n=5;
valuation(f(m,n),5)=2
------------------------
m=25;n=5;
valuation(f(m,n),5)=3
------------------------
m=5;n=25;
valuation(f(m,n),5)=2
------------------------
m=7;n=25;
valuation(f(m,n),5)=0

So m is similar to an enable signal in digital electronics, and if enabled then n can contribute to valuation increase. But only as much as the valuation of m.

[QUOTE=a1call;462965]The truth table I gave in OP is false. Please disregard it.

Here are some actual results:

------------------------
[COLOR="Green"]m=7;n=11;
valuation(f(m,n),5)=0[/COLOR]
------------------------
[COLOR="Green"]m=5;n=11;
valuation(f(m,n),5)=1[/COLOR]
------------------------
[COLOR="yellow"]m=7;n=5;
valuation(f(m,n),5)=0[/COLOR]
------------------------
[COLOR="Green"]m=5;n=5;
valuation(f(m,n),5)=2[/COLOR]
------------------------
[COLOR="Green"]m=25;n=5;
valuation(f(m,n),5)=3[/COLOR]
------------------------
[COLOR="Red"]m=5;n=25;
valuation(f(m,n),5)=2[/COLOR]
------------------------
[COLOR="Yellow"]m=7;n=25;
valuation(f(m,n),5)=0[/COLOR]

So m is similar to an enable signal in digital electronics, and if enabled then n can contribute to valuation increase. But only as much as the valuation of m.[/QUOTE]
Is this, some stupid guess the computer science function game ? BTW, Green = valuation as though f(m,n) is their product ; Red=f(m,n) has the same valuation as n ; Yellow= same valuation as m. What's important here ?

f(m,n) is a single algebraic function, not a program with if, elseif routines.

[QUOTE=a1call;462965]The truth table I gave in OP is false. Please disregard it.

Here are some actual results:

------------------------
m=7;n=11;
valuation(f(m,n),5)=0
------------------------
m=5;n=11;
valuation(f(m,n),5)=1
------------------------
m=7;n=5;
valuation(f(m,n),5)=0
------------------------
m=5;n=5;
valuation(f(m,n),5)=2
------------------------
m=25;n=5;
valuation(f(m,n),5)=3
------------------------
m=5;n=25;
valuation(f(m,n),5)=2
------------------------
m=7;n=25;
valuation(f(m,n),5)=0

So m is similar to an enable signal in digital electronics, and if enabled then n can contribute to valuation increase. But only as much as the valuation of m.[/QUOTE]

So maybe f(m, n) = prod_p p^(min(m, n) + m) where the product is over all primes p.

There are no Factorials. primorials, or Multifactorials in the function.

ETA There are also no int, floor, round or ceilings in the function. It is a classic algebraic function.

[QUOTE=a1call;462971]There are no Factorials. primorials, or Multifactorials in the function.

ETA There are also no int, floor, round or ceilings in the function. It is a classic [URL="https://en.wikipedia.org/wiki/Algebraic_function"]algebraic function[/URL].[/QUOTE]

what's the polynomial it's the root of ?

[QUOTE=science_man_88;462974]what's the polynomial it's the root of ?[/QUOTE]

Iff I understand it correctly the root is a function of n, but any of many different number of roots can be used.
This is assuming the root refers to the highest exponent in the function.

[QUOTE=a1call;462975]Iff I understand it correctly the root is a function of n, but any of many different number of roots can be used.
This is assuming the root refers to the highest exponent in the function.[/QUOTE]

a [URL="https://en.wikipedia.org/wiki/Zero_of_a_function"]root[/URL] is when a polynomial is 0.

[QUOTE=CRGreathouse;462970]So maybe f(m, n) = prod_p p^(min(m, n) + m) where the product is over all primes p.[/QUOTE]
Like I said there are no primorials in the function, but setting m as a primorial would be means of factoring n by GCD. But I am hoping for a more practical use.

[QUOTE=science_man_88;462976]a [URL="https://en.wikipedia.org/wiki/Zero_of_a_function"]root[/URL] is when a polynomial is 0.[/QUOTE]

Ok so solutions for m and n when f(m,n)=0
Scratch that.i don't know.i will let you know if I come up with a solution.

FYI I changed my last post.i don't know the root.

What would be the root of the function
2^x=0

[QUOTE=a1call;462980]What would be the root of the function
2^x=0[/QUOTE]

[TEX]2^{-\infty}\approx 0[/TEX] in theory . I may be wrong there though.

[QUOTE=science_man_88;462981][TEX]2^{-\infty}\approx 0[/TEX] in theory . I may be wrong there though.[/QUOTE]

That's what I thought too. But Wolfram alpha says none and infinity is not a number so it can't be a solution. Same way 1/0 converges to infinity but can't be equal to it and is addressed as undefined. But that is a can of worms best left to its own thread.

[QUOTE=a1call;462977]Like I said there are no primorials in the function, but setting m as a primorial would be means of factoring n by GCD. But I am hoping for a more practical use.[/QUOTE]

Functions don't have things "in" them. I think what you're trying to say is that your function can be expressed in closed form without using a symbol for primorial. But for that to make sense you're really going to need to explain what symbols you do allow and how you allow them to be joined. For starters, I assume you allow rational numbers, the field operations (+, -, /, *), and compositions of same. Anything else? Exponentiation, trig functions, other constants?

[QUOTE=CRGreathouse;462985]Functions don't have things "in" them. I think what you're trying to say is that your function can be expressed in closed form without using a symbol for primorial. But for that to make sense you're really going to need to explain what symbols you do allow and how you allow them to be joined. For starters, I assume you allow rational numbers, the field operations ([B]+[/B],[B] -[/B], /, *), and compositions of same. Anything else? [B]Exponentiation[/B], trig functions, other constants?[/QUOTE]
I can write the function using only integers, variables m and n and the bolded operators {()+-^}.
As with many functions there are ranges for the variables that give valid results.

ETA I wonder if a brute force can easily come up with the formula.:smile:

[QUOTE=a1call;462965]Here are some actual results:

------------------------
m=7;n=11;
valuation(f(m,n),5)=0
------------------------
m=5;n=11;
valuation(f(m,n),5)=1
------------------------
m=7;n=5;
valuation(f(m,n),5)=0
------------------------
m=5;n=5;
valuation(f(m,n),5)=2
------------------------
m=25;n=5;
valuation(f(m,n),5)=3
------------------------
m=5;n=25;
valuation(f(m,n),5)=2
------------------------
m=7;n=25;
valuation(f(m,n),5)=0[/QUOTE]

[QUOTE=a1call;462986]I can write the function using only integers, variables m and n and the bolded operators {()+-^}.
As with many functions there are ranges for the variables that give valid results.[/QUOTE]

Well, from #1 and #2 we can conclude that it must have m in it somewhere, and from #2 and #4 we can conclude that it must have n in it somewhere. If those were the only nulladic operators in the expression it would have to be m+n, m-n, n-m, m^n, or n^m. But it's easy to check that #4 does not hold for any of these, hence the expression has at least three nulladic operators. The third could me another copy of m or n, or else some integer.

[QUOTE=a1call;462986]I wonder if a brute force can easily come up with the formula.:smile:[/QUOTE]

No doubt brute force could come up with some formula meeting your criteria. I don't know that it would be the same one you have in mind, though.

[QUOTE=CRGreathouse;462991]
No doubt brute force could come up with some formula meeting your criteria. I don't know that it would be the same one you have in mind, though.[/QUOTE]

Well, then there would be a good chance that the found formula would have the same characteristics but evaluating to smaller integers than mine, and that would be a good thing.

But the main point off this thread is to discuss if such a function could be utilized in a practical (size not withstanding) factoring algorithm.

So, if there is such a function f(m,n), such that the factors of n can be present in f(m,n) only if they are also present in m (given factors of m will be present regardless and factors of n can increase the valuation by as much as the valuation in n).
Can such a function have uses in factoring. This is a unique behavior that seems of some potential use.

Here is an inefficient (Because forvec() is just too complicated to use [I hoped Pari-GP would have something more ergonomic like Mathematica's foreach]) programmatic equivalence of an ideal such function.:smile:


[CODE]print("\n\nBSL-100-A-p,function-of-m,n.gp\nBy a1call\n")
#

f(m,n)={
theResult =1;
forprime(p=2,m,
theValuationM = valuation(m,p);
theValuationN = valuation(n,p);
if(theValuationN > theValuationM, theValuationN =theValuationM );
theResult =theResult *p^(theValuationM +theValuationM );
);
return(theResult );
}

m=7*19^3
n=11*19^13
valuation(f(m,n),19)[/CODE][CODE]BSL-100-A-p,function-of-m,n.gp
By a1call

timer = 1 (on)
48013
462582818084827649
time = 4 ms.
6
[/CODE]

[QUOTE=a1call;463022]Here is an inefficient (Because forvec() is just too complicated to use [I hoped Pari-GP would have something more ergonomic like Mathematica's foreach]) programmatic equivalence of an ideal such function.:smile:


[CODE]print("\n\nBSL-100-A-p,function-of-m,n.gp\nBy a1call\n")
#

f(m,n)={
theResult =1;
forprime(p=2,m,
theValuationM = valuation(m,p);
theValuationN = valuation(n,p);
if(theValuationN > theValuationM, theValuationN =theValuationM );
theResult =theResult *p^(theValuationM +theValuationM );
);
return(theResult );
}

m=7*19^3
n=11*19^13
valuation(f(m,n),19)[/CODE][CODE]BSL-100-A-p,function-of-m,n.gp
By a1call

timer = 1 (on)
48013
462582818084827649
time = 4 ms.
6
[/CODE][/QUOTE]

Yes, that's just what I meant in post #13.

[QUOTE=a1call;463022]Here is an inefficient (Because forvec() is just too complicated to use [I hoped Pari-GP would have something more ergonomic like Mathematica's foreach]) programmatic equivalence of an ideal such function.:smile:


[CODE]print("\n\nBSL-100-A-p,function-of-m,n.gp\nBy a1call\n")
#

f(m,n)={
theResult =1;
forprime(p=2,m,
theValuationM = valuation(m,p);
theValuationN = valuation(n,p);
if(theValuationN > theValuationM, theValuationN =theValuationM );
theResult =theResult *p^(theValuationM +theValuationM );
);
return(theResult );
}

m=7*19^3
n=11*19^13
valuation(f(m,n),19)[/CODE][CODE]BSL-100-A-p,function-of-m,n.gp
By a1call

timer = 1 (on)
48013
462582818084827649
time = 4 ms.
6
[/CODE][/QUOTE]

the code you posted isn't practically usable in forvec as written anyways.

[CODE]forvec(X = v,seq,{flag = 0}):

Let v be an n-component vector (where n is arbitrary) of two-component vectors [a_i,b_i] for 1 <= i <= n, where all entries a_i, b_i are real numbers. This routine lets X vary over the
n-dimensional hyperrectangle given by v, that is, X is an n-dimensional vector taking successively its entries X[i] in the range [a_i,b_i] with lexicographic ordering. (The component with the hig
index moves the fastest.) The type of X is the same as the type of v: t_VEC or t_COL.[/CODE]

all this really means is for(x=1,3,for(y=1,10,seq)) is approximated by forvec(X=[[1,3],[1,10]],seq) where flag in the mentioned help tells if they should be nondecreasing ([TEX]x\le y[/TEX]),or strictly increasing ([TEX]x\lt y[/TEX])

A more efficient version:
[code]f(m,n)={
my(g=gcd(m,n), f=factor(g)[,1],p);
prod(i=1,#f, p=f[i]; e=valuation(m,p); p^(e+min(valuation(n,p),e)));
}[/code]

Testing
[code]v=vector(10^4,i,[random(10^6),random(10^6)]);
for(i=1,#v,call(f,v[i]))[/code]
(using the same vector for both calls) takes 2min, 37,589 ms for yours and 20 ms for mine.

Will be back to work tomorrow, so might as well spill the beans now.


f (m,n) = (m+1)^x + (m-1)^y

For integers m,n,x and y.
Where
x + y = n & y and n are both odd integers.



The closer x and y are together the smaller the evaluated function will be, but there is no algebraic way I know of to evaluate them such that x is guaranteed to be even.
So a purely algebraic formula would be:



f (m,n) = (m+1)^4 + (m-1)^(n-4)


For integers m,n
Where
n > 4 & n is odd