Mystery Operation V

[araver]

The series is back(*).

As we're still expanding in the universe, a small scout ship has encountered an anomaly near a binary system that has no planets only a few belts of asteroids. Getting closer to the system, they found the anomaly is centered in what seems to be an abandoned mining facility of alien design.

The crew landed and started exploring the corridors of the facility. No alien was to be found, except for some strange markings in all the corridors. Each corridor has two lines of dots parallel to each other, repeating along the corridor. Each corridor ends with a wall where another yet another series of dots is inscribed. All except one corridor that has no dots. Scans indicate that there is nothing behind the walls at the end of all corridors except for the one with no markings.

No guide or manual is available of course, but it stands to reason that some sort of alien algorithm or simple operation is behind this. So the crew noted all the number of dots in the corridors and walls, returned to the ship and unpacked their coffee reserves. This is going to take awhile...

Can you help them decipher it? (Blue and Red are number of dots in the first and second line along the corridors while purple dots can be found on the wall at the end of the corridor)

12 ||| 4 = 4
7 ||| 3 = 8
8 ||| 11 = 12
5 ||| 6 = 6
2 ||| 3 = 3
18 ||| 19 = 24
7 ||| 11 = 16

27 ||| 24 = ?

Spoiler

(*) Past challenges (no need to solve them to solve this one, but if you liked this one you'll probably like those too :P)

Mystery Operation I solved by k-man

Mystery Operation II solved by plainglazed

Mystery Operation III solved by curr3nt and plainglazed.

Mystery Operation IV solved by leakysheep.
 

 

 

[araver]

Note: Since the other challenges started with 2-3 cases and a question, I started this one with 7 cases. I will add more if needed after the 7th day which would be August 28th. But if anyone needs a clue before then, lemme know.

[plasmid]

Spoiler

The (2 ||| 3 = 3) and (7 ||| 3 = 8) along with (7 ||| 11 = 16) and (8 ||| 11 = 12) means we're dealing with a non-monotonic function, at least when the first number changes while the second is constant. Making a spreadsheet with the first value representing the x-coordinate and second value representing the y-coordinate, with the result being the value in the cell, didn't help a whole lot. Greatest common denominators are one of my favorite non-monotonic things to look for when we've got integers, but most pairs are relatively prime so that's little help.

Since we're in a binary star system do we know anything about the orbit of the mining station relative to the two suns? Because I tried interpreting that as a different sort of hint, but so far that hasn't gotten me anywhere.

Spoiler

 

01100
00100
00100

00111
00011
01000

01000
01011
01100

00101
00110
00110

00010
00011
00011

10010
10011
11000

00111
01011
10000

 

 

 

[araver]

There might be red-herrings in the OP. Unintentionally.

[araver]

New cases uploaded:

12 ||| 4 = 4
7 ||| 3 = 8
8 ||| 11 = 12
5 ||| 6 = 6
2 ||| 3 = 3
18 ||| 19 = 24
7 ||| 11 = 16

11 ||| 31 = 40

 

[araver]

3 more cases:

12 ||| 4 = 4
7 ||| 3 = 8
8 ||| 11 = 12
5 ||| 6 = 6
2 ||| 3 = 3
18 ||| 19 = 24
7 ||| 11 = 16

11 ||| 31 = 40

7 ||| 28 = 12

9 ||| 30 = 10

15 ||| 16 = 8

Edited September 7, 2016 by araver

[araver]

Well, this has stayed unanwered for a while (not sure anyone is still trying to solve this) so here are three new cases which should provide a big leap (but not necessarily the whole solution):

12 ||| 4 = 4

7 ||| 3 = 8

8 ||| 11 = 12

5 ||| 6 = 6

2 ||| 3 = 3

18 ||| 19 = 24

7 ||| 11 = 16

11 ||| 31 = 40

7 ||| 28 = 12

9 ||| 30 = 10

15 ||| 16 = 8

2 ||| 5 = 5

2 ||| 11 = 11

13 ||| 11 = 22

Edited September 24, 2016 by araver

[plasmid]

It's just that this is really hard.

We know there are operations on both the first and second input that make it non-monotonic (since 2 ||| 11 = 11, 7 ||| 11 = 16, 8 ||| 11 = 12; and 7 ||| 3 = 8, 7 ||| 11 = 16, 7 ||| 28 = 12). It's also alternating between increasing and decreasing multiple times based on the inputs with X ||| 11, so it's not just a matter of having the difference between the inputs (or some function along those lines) play a role. My best guesses are still that greatest common denominator or least common multiple or modular arithmetic are coming into play, but I don't see a solution emerging with any of those approaches. The strongest clue seems to be that so far, for any value of N, we've had 2 ||| N = N (so maybe it is monotonic in the special case where the first number is 2?)

[plainglazed]

At first was leaning more toward modulo vs multiples. Now thinking primes play a role. And/or that puzzle going around FB and other places where you add first digits and subtract second ones or similar like at http://brainden.com.

 

Difinitely been pulling my hair out daily crunching on this one, Araver. Cheers

[araver]

8 hours ago, plasmid said:

It's just that this is really hard.

We know there are operations on both the first and second input that make it non-monotonic (since 2 ||| 11 = 11, 7 ||| 11 = 16, 8 ||| 11 = 12; and 7 ||| 3 = 8, 7 ||| 11 = 16, 7 ||| 28 = 12). It's also alternating between increasing and decreasing multiple times based on the inputs with X ||| 11, so it's not just a matter of having the difference between the inputs (or some function along those lines) play a role. My best guesses are still that greatest common denominator or least common multiple or modular arithmetic are coming into play, but I don't see a solution emerging with any of those approaches. The strongest clue seems to be that so far, for any value of N, we've had 2 ||| N = N (so maybe it is monotonic in the special case where the first number is 2?)

Spoiler

It is hard in the sense that it is way easier to throw boulders into a deep lake than it is to take them out

Your observation is correct, your conclusion may not be, depending on what you meant. More exactly I see a problem/ambiguity in this sentence "It's also alternating between increasing and decreasing multiple times based on the inputs with X ||| 11, so it's not just a matter of having the difference between the inputs (or some function along those lines) play a role". If by some function you mean monotonic, yes. If you mean some function then, no. There may be lots of functions with interesting properties that are not monotonic but likewise simple in nature and a lot of combinations of such functions may lead to increasing/decreasing patterns. Not saying the solution is one of them, just that the class of simple/interesting functions is ... big.

"The strongest clue" that you mentioned is intentional and the hypothesis is correct. And also in the spirit of encouraging, there may be similar clues that can help with establishing a pattern, it doesn't necessarily have to be a "1-click-type solution". It is harder for me to figure out how everyone's brain work so I don't know if what I am saying will help you or not.

 

3 hours ago, plainglazed said:

At first was leaning more toward modulo vs multiples. Now thinking primes play a role. And/or that puzzle going around FB and other places where you add first digits and subtract second ones or similar like at http://brainden.com.

 

Difinitely been pulling my hair out daily crunching on this one, Araver. Cheers

Spoiler

Those are all valid hypothesis. 

I would however try to help you stay with more hair on rather than out, so lemme throw in a hint: "it's not like that puzzle on FB/other places".

I am glad that you are trying to solve it (which is why I hit Reply  ), but I can't help myself talking about it while you are trying, so I used spoilers (even though there are no major spoilers in my responses).

[plainglazed]

Still at it araver.  Probably obvious to any out there checking this thread out but gonna put it out there anyway:

Spoiler

If both numbers of the operation are prime, the resulting number is two less than their sum.  Been working with the assumption that could be the sum of the difference of their factors i.e 7 ||| 11 = 16  could be (7-1)+(11-1).  So instances where you have a prime and a nonprime input as in 8 ||| 11 = 12  the 8 would have to yield 2.  From similar instances: 6-->2, 18-->6, 24-->6.  So been playing with prime factors, factored pairs, multiplicities etc but to no avail as of yet.  Running out of coffee.  Got    to    get...

 

[araver]

2 hours ago, plainglazed said:

Still at it araver.  Probably obvious to any out there checking this thread out but gonna put it out there anyway:

  Hide contents

If both numbers of the operation are prime, the resulting number is two less than their sum.  Been working with the assumption that could be the sum of the difference of their factors i.e 7 ||| 11 = 16  could be (7-1)+(11-1).  So instances where you have a prime and a nonprime input as in 8 ||| 11 = 12  the 8 would have to yield 2.  From similar instances: 6-->2, 18-->6, 24-->6.  So been playing with prime factors, factored pairs, multiplicities etc but to no avail as of yet.  Running out of coffee.  Got    to    get...

 

Spoiler

You're on the right track. Just one or two stations to go.

The assumption holds.

From there you have 2 options:

1. The examples could give you another assumption. And from there another look would yield the "Aha" moment.

2. Brute force the examples and reverse engineer the most plausible explanation for the sequence.

So one or two stations to go depending on how much coffee ...

 

[plainglazed]

Ok, think I'm close:

Spoiler

Each operand n is converted to the number of positive integers less than n and relatively prime to n.  Then simple addition of the two converted operands yields the result. 

I said I think this is close because if an n is not prime and converts to a multiple of 4, then it appears that result must be halved before adding to the other half of the operation.  Knowing araver, gotta think there is a more elegant way to describe what appears to be a need for further reduction in certain cases.

For example:

5 ||| 6 = 6

(1,2,3,4) ||| (1,5) = 6

4 + 2 = 6

 

12 ||| 4 = 4

(1,5,7,11) ||| (1,3) = 4

4/2 + 2 = 4

 

So:

27 ||| 24 = ?

(1,2,4,5,7,8,10,11,13,14,16,17,19,20,22,23,25,26) ||| (1,5,7,11,13,17,19,23) = ?

18 + 8/2 = 22 ???

 

 

[araver]

2 hours ago, plainglazed said:

Ok, think I'm close:

  Reveal hidden contents

Each operand n is converted to the number of positive integers less than n and relatively prime to n.  Then simple addition of the two converted operands yields the result. 

I said I think this is close because if an n is not prime and converts to a multiple of 4, then it appears that result must be halved before adding to the other half of the operation.  Knowing araver, gotta think there is a more elegant way to describe what appears to be a need for further reduction in certain cases.

For example:

5 ||| 6 = 6

(1,2,3,4) ||| (1,5) = 6

4 + 2 = 6

 

12 ||| 4 = 4

(1,5,7,11) ||| (1,3) = 4

4/2 + 2 = 4

 

So:

27 ||| 24 = ?

(1,2,4,5,7,8,10,11,13,14,16,17,19,20,22,23,25,26) ||| (1,5,7,11,13,17,19,23) = ?

18 + 8/2 = 22 ???

 

 

Yup, that is close.

EDIT: But the result for the question in the OP is incorrect.

However, to get your attention, a couple more cases that might help.

2 ||| 15 = 5

5 ||| 21 = 10

7 ||| 28 = 12

7 ||| 40 = 10

Edited October 24, 2016 by araver

[araver]

Marking plainglazed's answer as correct since there are no other contestants, even though my answer differs a bit.

For the record:

27 ||| 24 = 18 + 2 = 20

The explanation is that PG's answer is correct up to a point, spoiler below for comments on his solution

Spoiler

plainglazed: "Each operand n is converted to the number of positive integers less than n and relatively prime to n.  Then simple addition of the two converted operands yields the result. "

Araver: True, there is a function f such that a ||| b = f(a) + f(b) = c

plainglazed: "I said I think this is close because if an n is not prime and converts to a multiple of 4, then it appears that result must be halved before adding to the other half of the operation.  Knowing araver, gotta think there is a more elegant way to describe what appears to be a need for further reduction in certain cases."

Araver: Indeed

1) if n is prime f(a)=a-1

Examples:  f(2) = 1, f(3) = 2, f(5) = 4, f(7) = 6, f(11) = 10, f(13) = 12, f(17) = 16, f(19) = 18, f(23) = 22.

2) if n is not prime and converts to a multiple of 4 f(a)<=a/2.

Examples: f(4) = 2, f(8) = 2, f(12) = 2, f(16) = 4, f(20) = 4, f(24) = 2, f(28) = 6, f(32) = 8, f(36) = 8.

Still don't see a pattern?

Good, because it is not obvious.

3) if n is not prime the function is more complicated than it seems. Let's see if n = p*q where p and q are distinct primes

f(6) = 2 where f(2)=1 and f(3)=2

f(10) = 4 where f(5)=4 and f(2)=1

f(15) = 4 where f(5)=4 and f(3)=2 

It looks like a maximum at this point, let's go further

f(22) = 10 where f(11)=10 and f(2)=1

f(21) = 6 where f(3)=2 and f(7)=6

f(33)=10 where f(3)=2 and f(11)=10

So one could conjecture that f(p*q)=max(f(p),f(q)) where p and q are different primes. *It is actually close but not true.

This works for 3 numbers as well see: 

f(30)=4 where f(2)=1, f(3)=2 and f(5)=4

4) Let's look at f(p*p) where p is a prime

f(4) = 2 where f(2)=1

f(9) = 6 where f(3)=2

f(25)=20 where f(5)=4

It almost looks like f(p*p)= p*f(p)= p*(p-1)

The above does not explain what happens in the following cases:

f(8)=2 where f(2)=1, f(4)=2

f(16)=4 where f(4)=2, f(8)=2

f(32)=8 where f(16)=4, f(2)=1 

f(18)=6 where f(2)=1, f(6)=2 and f(3)=2 and f(9)=6. 

Confused?

Yes, PG had the correct idea, that there must be an elegant way to describe the series.

You can still think about it before clicking the following:

Spoiler

The definition of f (or one of the definitions actually) is the Carmichael function.  see https://en.wikipedia.org/wiki/Carmichael_function

f(n)=b where b is the smallest positive integer such that a^b = 1 (mod n) for every a coprime with n.

Note that Euler's totient function is similar

g(n)=c where c is the number of integers up to n that are relatively prime to n.

However Euler's totient function (which was featured in a previous Mystery Operation btw ) is multiplicative, hence easier to discover.

Since Euler's theorem states a^g(n)=1 (mod n) it is natural that  f(n) <= g(n)

First number where they actually differ is 8.

f(8)=2 while g(8)=4

It is easy to see that 7^2=1 (mod 8), 5^2 = 1 (mod 8), 3^2=1 (mod 8). So while it is true that a^4=1 (mod 8) for every a coprime with 8, the power of two is sufficient.

And yes, there is a recursive definition that makes more sense

f(n)= lcm [f(p1^a1), f(p2^a2), ... , f(px^ax)]

where n =  p1^a1* p2^a2 * ... * px^ax is the unique prime decomposition of n.

And back to our series, the way to decipher it would have been to guess a composition relation which in this case isn't that simple as it it isn't a multiplicative function. In this case, the hidden formula was:

f( lcm(a,b) ) = lcm [f(a), f(b)] 

which gave for f(24) = f( lcm(3,8))= lcm [f(3), f(8)]= lcm (2,2)=2.