Interesting Sequence? (gcd(parts) = median(parts))

[Austen F]

Hi all,

I’m exploring an integer sequence that might be interesting for the OEIS. I'm a complete amateur so I figured I should get feedback here before trying to create a draft: 

Definition: Consider ordered compositions of n (i.e., sequences of positive integers summing to n). For each composition, compute the gcd of all parts and the median of the multiset of parts. For even-length compositions, I take the lower-middle of the sorted parts as the median. The sequence counts the number of compositions of n where:

gcd(parts) = median(parts)

Known Terms:  1, 2, 4, 8, 11, 26, 44, 89, 165, 337, 638, 1292, 2521, 5044, 9931, 19859, 39355, 78462, 155970, 311161, 619221, 1234838, 2460906, 4907970, 9785136

(This is as far as I've gotten with a simple python script in google colab but I can probably take it a bit further.)

• The sequence begins looking like powers of 2 but then diverges. The behavior to me seems irregular and nontrivial?
• The closest sequence to this currently documented is A130711 (my inspiration) which behaves differently

Would this sequence be suitable as an OEIS submission, or is it too simple/arbitrary? Any references to additional related work would also be appreciated.

Thanks,

Austen

[Robert Israel]

I would say it is interesting and not at all trivial. Please do submit it.

Cheers,

Robert

--
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/00c305a7-b89c-4f89-afd2-4b587610a7a3n%40googlegroups.com.

[Brendan]

Let g be the gcd. Since g must be present, it must be the smallest part, and since it must be the median, at least half of the parts must be equal to g.

So an alternative description is compositions of n with at least half the parts equal to the smallest part, and all parts being a multiple of the smallest part.

This will give a summation with binomial coefficients. I'll give someone else the pleasure.

Brendan.

--

[Austen F]

Hey Brendan,

Thanks for the insight! I tried to work out out a formula based on your observation. For the primitive sequence b(n) (compositions where gcd = median = 1):

b(n) = 1 + Σₖ₌₂ⁿ⁻¹ Σⱼ₌₁^min(⌊k/2⌋, n-k) C(k,j) · C(n-k-1, j-1)

Where k is the number of parts, j is the number of parts greater than 1, C(k,j) chooses positions for the non-ones, and C(n-k-1, j-1) distributes the remaining sum among those j parts (each ≥ 2).

I verified this matches the known values discovered by Alois P. Heinz up to n=149. Having spoken with him, b(n) probably merits its own sequence entry so the formula for gcd(parts) = median(parts) can be:

a(n) = Σ_{d|n} AXXXXXX(n/d)

Does this seem right?

Thanks, 

Austen

[Brendan]

That's the sort of thing I expected, yes.  Cheers, Brendan.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/56f3d5d9-0f74-416d-ab81-ed8e47f764edn%40googlegroups.com.