Math Q&A challenge (Part 11)

agentredlum

Math Team
Jul 2011
3,372
234
North America, 42nd parallel
Actually, if we look at icemanfan's approach it tells us exactly where to put powers of single primes. Put 1 in set A , then set A also gets any prime divisor of the form p^3 , p^5 , p^6 , p^9 , p^10 , p^12 , p^13 , p^15 , ... Set B gets the other powers of single primes, p, p^2, p^4, p^7, p^8, p^11, p^14, ... . I have confirmed this using the 'domino effect' idea I mentioned in a previous post, you must put p^2 in set B if 1 is in set A, then continue the argument, p^3 must go in set A otherwise we won't be able to match the product p*p2 in set B, next consider that we can't put p^4 in A since there is no way to match 1*p^4 in B. Continue... These steps are non-negotiable regardless of whether the divisors are square free or not AND regardless of whether we are talking about partitioning the entire set of positive integers or the set of divisors of any particular positive integer.

So it is no wonder that in the Hoempa example, partitioning the divisors of 54, 9, which is the square of the prime 3, must go in set B, while 27, which is the cube of the prime 3, must go in set A.

Much harder (for me) is to figure out where divisors of the form c*p^n go, where c is some composite with prime factors to arbitrary powers, I'm trying though. It's easy to do this for small numbers as a 'domino effect', but for large numbers with many prime factors it is hard for me unless we can come up with some formula based on the exponents of the prime factorization of each divisor ... maybe?

It would be a good idea to figure out a formula for the exponents of 2 in the icemanfan example.

Note* If this turns out to have some connection to the J-semigroup discussed elsewhere in MMF, I will be pleasantly surprised ... it's not out of the question!

:D
 

Hoempa

Math Team
Apr 2010
2,780
361
[color=#00AA00 said:
agentredlum[/color]]Much harder (for me) is to figure out where divisors of the form c*p^n go, where c is some composite with prime factors to arbitrary powers, I'm trying though. It's easy to do this for small numbers as a 'domino effect', but for large numbers with many prime factors it is hard for me unless we can come up with some formula based on the exponents of the prime factorization of each divisor ... maybe?
I gave an algorithm for that, but a formula seems hard. Let m be the exponent. Then
If ceil(2*m/3) mod 2 = 0 then m in A else m in B
seems quite good, but isn't 100% accurate.

Let 0 be in set A.
Let m be the exponent, m is a non-negative integer.
define f(m) is if m and m+1 are in different sets then f(m) = 0 else f(m) = 1
Examples:
f(5) = 0 since 5 and 6 are in the same sets (in set A)
f(24) = 1 since 24 and 25 are in different sets (24 in set A and 25 in set B).
Then it seems that f(m) is 0 if m = (2*4^c - 1) mod 4^c for any positive integer c.
We have if \(\displaystyle \left(\sum_{k=0}^m f(m)\right) \bmod 2 = 0\) then m + 1 in A else m + 1 in B. Remember 0 is in set A.
 

agentredlum

Math Team
Jul 2011
3,372
234
North America, 42nd parallel
Let's see your algorithm at work. Consider

\(\displaystyle x \ = \ 2^7 \cdot 7^{31} \cdot 11^{15}\)

We know there must be a good partition of this because the number of distinct positive divisors is 8*32*16 = 2^12

Put 1 in set A. Now using your algorithm can we determine which set an arbitrary divisor must go? Say the divisor \(\displaystyle \ \ 2^5 \cdot 7^{23} \cdot 11^{12} \ \\) , will it go in set A or set B ?

CRG said there is a partition of the positive integers , fine , put 1 in set A and consider the positive integer \(\displaystyle \ \ 5^{2013} \cdot 19^{13} \cdot 67^{541} \cdot 101^{3794} \cdot 127^{127} \ \\) can your algorithm tell us which set we have to put this monster in ?

I am not criticising your algorithm (actually , i don't understand it very well so i can't criticise it) , merely trying to determine how useful it can be for using it in a proof.

kindest regards,
-agentmulder.

:)
 

Hoempa

Math Team
Apr 2010
2,780
361
We'll construct our own numbersystem now.
By concatenation:
fgh where f in {0, 1, 2,...,7}, g in {0, 1, 2,..., 31}, h in {0, 1, 2,..., 15}
To convert fgh to decimal, compute (31 + 1)(15 + 1) * f + (15 + 1) * g + h = 512 * f + 16 * g + h
we have f = 5, g = 23, h = 12 so fgh = 2940.

I find 980 numbers i in {1, 2,..., 2940 - 1 = 2939} of the form 2 * 4^c - 1 mod 4^(c + 1) where c in {0, 1, 2, 3, 4, 5}
so \(\displaystyle \left(\sum_{k=0}^m f(m)\right) \bmod 2 = 2939 - 980 \bmod 2 = 1\) gives m + 1 = 2940 is in B.
Since 2940 is in B, so is your number.

[b said:
agentredlum[/b]]can your algorithm tell us which set we have to put this monster in ?
I don't think you'd want to put every element of N in a group to prove such a partition exists, but I believe mine can't. My intuition (wrongly perhaps) tells me no such partition of the positive integers exists.
 

CRGreathouse

Forum Staff
Nov 2006
16,046
936
UTC -5
Hoempa said:
Since 2940 is in B, so is your number.
This answer is correct. Does that mean my problem has been solved? (I haven't caught up with the recent flurry of posts!)
 

agentredlum

Math Team
Jul 2011
3,372
234
North America, 42nd parallel
That depends , are you asking for a proof that n = 2^k are the only solutions? We haven't been able to prove that. Is it true that n = 2^k are the only solutions? I don't understand Hoempa's algorithm so i can't comment on it but i do understand that even if the algorithm is flawed there is still a 50 - 50 chance it will give the right answer for any particular divisor because there are only 2 sets in the partition. Hoempa himself has indicated that the algorithm is not foolproof and i respect his derivation of it as well as the recursive formula given by icemanfan in his example using powers of 2 which can be generalized to any power of a single prime , as icemanfan indicates at the beginning of his post.

:)
 

CRGreathouse

Forum Staff
Nov 2006
16,046
936
UTC -5
It looks like Hoempa's algorithm works properly -- but it's a bit hard for me to understand. (There is an easy characterization of the correct answer.)
 

Hoempa

Math Team
Apr 2010
2,780
361
How could I explain the algorithm to you? I've coded most of this and quite some work on pieces of paper but I
don't know what to tell you. I'm not sure whether it's solved and my doubts are hard to express without assuming you understand the algorithm.

The algorithm merely follows these steps:
To place a number m, say 60, in eighter set A or B,
- wlog, place 1 in A.
- Find the number n >= m that has 2^k divisors. 60 = 2^2 * 3^1 * 5^1. For every primefactor, the multiplicity must be of the form 2^l - 1. 2 isn't. The next number higher than 2 of this form is 3, so n = 2^3 * 3^1 * 5^1 = 120.
- find an expression that gives a value that indicates whether m goes in A or B. The computation of this value is I think what is hard for you.
Let n = p1^b1 * p2^b2 * p3^b3 * ... where pi are primes.
Let m = p1^c1 * p2^c2 * p3^c3 * ... (wher pi are primes, same as for n).
Then the expression becomes
(b2 + 1)(b3 + 1) * c1 + (b3 + 1) * c2 + c3
for 120, this is (1 + 1) * (1 + 1) * c1 + (1 + 1) * c2 + c3 = 4 * 2 + 2 * 1 + 1 = 11. Find the amount of values of the form 2^d - 1 < 11 - 1. These are 1, 5, 9, 7. 4 of them.
Subtract this amount from the value we found. Gives 11 - 4 = 7. 7 is odd so 60 comes in B.

I think I have figured out how to split the naturals in two sets, though I don't know for sure if 60 comes in B just if we consider the divisors of 120 or for the divisors of all numbers that divide 60 and have 2^k divisors.
Also, I don't know if we can say: when 11, the value we computed, is written in base 2, gives 1011, the amount of 1 (or sum of digits) is odd so 60 is in B.

I don't know whether we say this is solved.
 
Sep 2012
764
53
British Columbia, Canada
Hoempa said:
I don't know whether we say this is solved.
Well how about we say it is and continue on with the game, OK? :D
 

CRGreathouse

Forum Staff
Nov 2006
16,046
936
UTC -5
Works for me. Sorry, haven't had much time to post here recently...
 
Similar Math Discussions Math Forum Date
General Math
General Math
General Math
General Math