Formula for partitions
Ali Sada
Hi everyone,
Hope all is well. I derived this formula for partitions from A382250 (thank you Maximilian!) I would really appreciate your help checking it.
A(n)= floor((q^(m*(m+1)/2) * (q^n + G)) / ((q - 1)*(q^2 - 1)*...*(q^m - 1))) mod q
q = 2^(n + 2)
m = floor(n / 2)
G = (q^(n - m) - 1) / (q - 1)
Best,
Ali
Fred Lunnon
--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/CACOfRNqQ6urdkyttQUCMoATCzpHfDrgvQ70uOnyjfJdY3%3D8O%3DQ%40mail.gmail.com.
Ali Sada
To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAN57Yqv2-AMYxdXHqcDBfBMCkp8USxwAzQRV8Hxw%2Bh%2BC614jmA%40mail.gmail.com.
Gareth McCaughan
I'm not sure how A382250 helps, and consequently I'm not sure whether I'm just restating things Ali already knows, but it seems like this is approximately a disguised version of the usual generating function for the partition numbers:
sum p(k) x^k = product 1/(1-x^k).
Let q be a "large enough" positive integer (apparently it will turn out that 2^(n+2) will do) and set x = 1/q. Then we have
sum p(k) q^-k = product 1/(1-q^-k)
and hence sum p(k) q^(n-k) =q^n product 1/(1-q^-k)
and the LHS consists of (a) terms that are multiples of q, (b) the term p(n), and (c) terms involving q^negative. If q is large enough then (handwave handwave, details to be supplied later) the terms (c) will add up to < 1, so the remainder on dividing floor(this) by q will be exactly p(n).
Let's take a look at the RHS. Pick a "suitable" positive integer m (it will turn out that floor(n/2) will do). Multiply the first m factors by q, q^2, ..., q^m and leave the rest alone. Then the RHS is q^n . q^(m(m+1)/2) . (q-1)...(q^m-1) . product {k>m} 1/(1-q^-k).
We've nearly got Ali's formula now. Aside from verifying that his choice of q is large enough (which I think should be very easy), we need to check that with his choice of m and definition of G, (q^n+G)/q^n is close enough to product {k>m} 1/(1-q^-k) that the integer parts of
q^n product {k<=m} 1/(1-q^-k) product {k>m} 1/(1-q^-k)
and
q^n product {k<=m} 1/(1-q^-k) (q^n+G)/q^n
are equal.
So, the two things we want to be close to one another are product {k>m} 1/(1-q^-k) and 1+G/q^n. We can write G = q^(n-m-1)+q^(n-m-2)+...+q+1, so this equals 1 + (q^-(m+1)+q^-(m+2)+...+q^-n).
It certainly seems like this should be close to product {k>m} 1/(1-q^-k), which super-crudely is approximately product {k>m} 1+q^-k, which in turn is approximately sum 1+sum {k>m} q^-k, which is roughly what we got for G/q^n.
So then we would need to get a lower bound (call it B) on how far the thing we need the integer part of is from the nearest integers, such that B is also an _upper_ bound on how far our infinite product can be from G/q^n. It's late enough at night where I am that I prefer to just go to bed :-).
Again, I've no idea whether this is just repeating what Ali has already done and not shared the details of with us. Ali, when you say you derived your formula, do you mean you deduced it? (Or that you mostly deduced it, but with some gaps, like what I did above?) If so, and if you want your deduction checked by others, it seems like you should share your (?partial?) proof and not just your conclusion. On the other hand, if you mean you conjectured it, the rather handwavy calculations above give some indication of why it might be true, but it definitely needs more detailed analysis and this feels like the kind of thing that might turn out to break down at n=10^10^180 or something :-).
--
g
Ali Sada
| Wed, Jan 15, 2025, 12:19 AM | |||
| ||||
Hi everyone,
Hope all is well. I have been working on this array for a while but I’m not sure if it exists in the OEIS. In any case, I have put the notes below and I would really appreciate any feedback.
We start with two ‘cells’
|
|
|
|
Then 4 cells
|
|
|
|
|
|
|
|
|
|
|
|
Then 8 cells
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
And so on (2^n).
The rule here is that we add the adjacent cells that have the same color.
For example, the shape below is 3.
|
|
|
|
While the shape below is 2+1
|
|
|
|
And this one is 1+1+1
|
|
|
|
So, for the n=3 shape we have
3
1+2
1+1+1
2+1
2+1
1+1+1
1+2
3
To construct the array, we number these partitions in order from 1 to 2^n.
Then we start with a new sheet, and we put the partitions in order. If the partition is unique (so far) we put it in the first row. The equal partitions below each other.
n=1
|
1 |
|
2 |
n=2
|
1 |
2 |
|
4 |
3 |
n=3
|
1 |
2 |
3 |
|
8 |
4 |
6 |
|
|
5 |
|
|
|
7 |
|
n=4
|
1 |
2 |
3 |
4 |
6 |
|
16 |
8 |
5 |
13 |
11 |
|
|
9 |
7 |
|
|
|
|
15 |
10 |
|
|
|
|
|
12 |
|
|
|
|
|
14 |
|
|
n=5
|
1 |
2 |
3 |
4 |
5 |
6 |
11 |
|
32 |
16 |
9 |
8 |
7 |
10 |
22 |
|
|
17 |
15 |
25 |
13 |
12 |
|
|
|
31 |
18 |
29 |
20 |
14 |
|
|
|
|
24 |
|
26 |
19 |
|
|
|
|
30 |
|
28 |
21 |
|
|
|
|
|
|
|
23 |
|
|
|
|
|
|
|
27 |
|
n=6
|
1 |
2 |
3 |
4 |
5 |
6 |
8 |
10 |
11 |
13 |
22 |
|
64 |
32 |
17 |
16 |
7 |
18 |
57 |
12 |
19 |
52 |
43 |
|
|
33 |
31 |
49 |
9 |
--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/510a2426-0e71-4c16-9a77-636f25c77cd5%40pobox.com.
Gareth McCaughan
Thank you very much for your thoughtful response. I really appreciate it. I am not a mathematician, and the only knowledge I have about partitions came from two YouTube videos, so I apologize if I couldn't provide the necessary useful information. I designed a 3-D array and sent it last year to this group. Please see below. Maximilian formalized it mathematically in A382250. I am not so good with notations, but I like numbers and can sometimes follow their development. In the array, the x-coordinate of the top two cells is P(n). Their labels are known: (1,2,3,6,11,22,43,...) and their colors also, and I found that they follow a very simple and consistent pattern.
I still have absolutely no idea where you got your formula from. It seems like a fairly natural thing for someone familiar with the generating function for the partition numbers to come up with (though it's not obvious to me where the choice of G comes from) and completely baffling as something that somehow occurred to someone who isn't a mathematician and knows only two YouTube videos' worth of information about partitions.
The reason I'm being inquisitive about this is twofold. First, it's often much easier to find a proof of something when one has some idea where it comes from. I'm absolutely certain you didn't just look at the numbers and say "ah, this looks to me like floor((q^(m*(m+1)/2) * (q^n + G)) / ((q - 1)*(q^2 - 1)*...*(q^m - 1))) mod q". (Maybe if you were literally Srinivasa Ramanujan, but I bet you aren't. Hardly anyone is.)
So if you got to this rather intricate formula by spotting patterns, I bet there are some steps along the way that you also got to by spotting patterns, and it may be that some of those are useful building blocks for a proof as well as for a conjecture.
The second reason is that in these days of miracle and wonder, one possible explanation when a non-mathematician finds something that feels like it would be much easier for a mathematician to find is that actually it was an AI system that found it. I don't have any particular objection to using AI systems to find mathematical conjectures, but I do think that (1) if you do that you should also ask them to prove their conjectures, which as we've all heard some of them are getting pretty good at, and (2) if you do that then you should say so.
(Why? Two reasons. First, to avoid dishonesty or the appearance of dishonesty. Second, because the likely next fruitful steps if you found the conjecture yourself and the likely next fruitful steps if you got it from an AI system are probably different. For instance, if you found it yourself then -- see above -- it's worth asking how you got there; where did the idea of putting (q-1)(q^2-1)... in the denominator come from? why take about n/2 terms of that product rather than some other number? why G? etc. -- but if the answer to all of those would be "I dunno, this is just what came out of the AI system" then asking those questions may be a waste of time; on the other hand, if you found it yourself but it was purely a matter of intuitive pattern-spotting in tables of numbers, there's no point asking you for proofs, whereas if an AI system found it then it's likely that it had "in mind" (whatever that means for an AI system) something like the argument I sketched, and asking it to prove its conjecture might produce a valid proof (or a proof with fillable gaps, or something).
(Finding a human mathematician who wants to review an AI system's proof of this might be more difficult, I suppose, depending on whether the proof is half a page or a hundred pages.)
--g
Ali Sada
Hi Gareth,
Thank you again for your response.
I have been working on this array for more than 4 years now and I have created over 200 Excel files for it. Please see some samples attached. I promise you two things: 1) Ramanujan would have needed only one of these files and less than 30 minutes to reach this formula. 2) There is no AI on earth that is so disorganized and that can come up with such silly names for its files.
You gave the solution in your first email. Please take a look at the Excel file attached. You can notice the jumps (for example, 19 came from 14, which came from 3 which came from 2 which came from 1). If you take the differences they will add up to n. Changing the order does not create a new column. It gives another tile within the same column. So, each column gets a unique “fingerprint” which is the partitions of n.
The array showed that each column corresponds to one partition of n, but we still need a way to count those partitions without listing them. As you said we choose q = 2^(n+2)
as a large number base to encode all the partition counts in different positions without overlapping. Then “floor” removes the unwanted fractional tail and mod q extracts exactly the count for n the number of columns.
I expressed more than once on this list that I use ChatGPT because I am not capable of using math language to write down my ideas. I used to depend on friends on this list and the OEIS editors to write them for me, and I thank ChatGPT for spearing them the agony of reading my emails. But that doesn’t mean ChatGPT thinks for me. They are my ideas, and the AI is merely a glorified calculator, editor, and search engine. It will never replace human thinking because it doesn’t enjoy discovering. It was I who discovered this array, discovered there were three types and gave them the colors, discovered the “bloodlines” of the colors, discovered the jumps, and many other things.
Thank you again for your email, and I apologize to everyone but I had to respond.
Best,
Ali
--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/b44d8d28-819f-4870-8065-00257c049bb7%40pobox.com.
