The Open Problem Garden is a fledgling site that deserves more contributions.
There's not very much information about the purpose of the site, but from what I can gather, it's intended to be a repository for open problems in mathematics and theoretical computer science. I think that's a great idea, but the number of contributions is still pretty small (only about 150 problems so far). If you know some good open problems, please consider adding them to the site.
I added a a problem about discrete iterations, which I'll repeat here because it is so easy to state, yet frustratingly difficult to solve.
Start with two integers, a and b, with a > b > 0. Now repeatedly replace b with a mod b, counting the number of steps it takes to get to 0, and call this P(a,b). For example, if we start with a = 35 and b = 22, we get
35 mod 22 = 13
35 mod 13 = 9
35 mod 9 = 8
35 mod 8 = 3
35 mod 3 = 2
35 mod 2 = 1
35 mod 1 = 0
It took 7 steps to get down to 0, so P(35,22) = 7.
The question is, at what rate does P(a,b) grow? It's not hard to see that for some a, P(a,b) can be as big as Ω(log a). (Take a = lcm(1,2,..., n)-1 and b = n.) But what's a good upper bound? I conjecture it's O((log a)2), but the best that's been proven so far is O( a1/3).
Oh, and by the way -- I offer $50 for the solution to this problem.
Subscribe to:
Post Comments (Atom)
7 comments:
You mean, P(35,22) = 7, right? Nice problem, thought: I think I won't be the one who earns so much as 50$ ;-)
Thanks for the correction; I've fixed the main text.
I've tucked your problem somewhere between the middle and the back of my mind.
I wonder what moderation there is for the site's entries (I couldn't glean it from my quick perusal). That is, would this site ever be a crutch for those not wishing to do a thorough literature search, perhaps to determine whether a problem is truly open or not?
It has some interesting structure:
(first 1000 as--brighter is greater magnitude)
responding to david swart..
My name is Matt DeVos, I'm one of the co-creator's (and moderators) of the Open Problem Garden (the other is Robert Samal). At the moment, we do a small amount of moderation, mostly either demoting problems which we feel are lacking to our second tier location, and moving solved problems to the solved problem section (both can be found by following the "more" link in the Navigate menu).
I think in the long run this site has a chance of being quite useful for determining the status of a problem, but only if we get a good community of people using it.
Matt
PS - to Jeffrey Shallit, thanks for posting your lovely problem!
This is about open problem garden.
Is there a way to view the page? All I can see is a tex script.
I would contact the people who run the site, not me.
Post a Comment