At some point you mentioned it was possible to divide N by a backref. Do you actually have a way to do this in the general case? The chinese trick is cool but afaict it only works if (N / backref) is coprime with backref or backref - 1.

Never mind, I found it

Aaand totient followed easily

Returns a match of length phi(N), no (?*), no (?<=), 194 chars ungolfed. I'd say this is vastly easier than fibonacci or abundant.

@Grimy Excellent! Can you give me a hint please? I have no idea how to do it.

All I can think of is take all base prime factors p, and multiply by (p-1)/p. But I can't think of any way to do that for all of them.

This is essentially my algorithm as well

There are two numbers to keep track of: current product, and last prime factor added to the product

These two numbers can be stored in a single number, with a trick similar to the one used on log2

@Grimy You need much more than just that. You need the set of primes that remain to add to the product. That's three numbers.

Please give a better hint. Or if you don't want to explain it to me so I can implement my own version of it, just post it on Calculate Euler's totient function.

Either way you'd be credited. If I ended up making one less than 194 characters, I'd credit you with the idea, and if not, then you'd be the one to post anyway.

I don’t understand why you’d need a third number. If you add them in order, the set of primes that remain to be added are those > the last prime added.

How can you keep track of them to add them all?

Maybe you're just so amazing at doing this that you don't understand what the challenge of it is...

To know what prime to do next, you need to have the set of primes that haven't been done yet.

Which in the simplest way would mean having the original N with all the already-handled primes divided off. But there can't be room for both that and your two-numbers-in-one.

Just find the smallest prime factor that’s > the last prime added

Oh

What I thought of was using my same algorithm to find the smallest factor that shares all prime factors. i.e. has one of each base prime in it

But that was unhelpful.

@Grimy That's definitely not going to work

Not all primes are factors of N

Did you implement an algorithm that doesn't actually calculate totient, but calculates something else?

I only checked up to 60

Lemme check further

You're missing something in the explanation

Not all primes are factors of N

Simply finding the next smaller is not going to be useful for anything

The first number with a gap in its factors is 2*5=10, so the problem should happen well under 60

So I think you're just missing something in your explanation, not your regex

I meant next smaller prime factor

Not next smaller prime

How can you find that without having N available for testing against?

If you're in a loop doing something for each prime, you no longer have N to find factors for

Yeah but you have the product

Product of what?

N * (p-1) / p

But that's going to destroy information

It's going to add smaller primes to the factorization

It has the same “smallest prime factor > p” as N

Prime factors smaller than p are ignored anyway

But how can you keep track of both N * (all of the (p-1)/p for the smaller primes handled so far) and which is the largest prime you've handled so far?

The largest prime handled so far is still going to be less than that

so they can't be combined into one number

Let M be the biggest prime factor of N. First number is always a multiple of M, second number is in the range 2..M.

So just add them together (- 1), then do a modulo to extract them.

Also I just checked up to 10000, no errors.

Ahhhhh

That's the only part you had to say. Modulo by N's largest prime factor

It's basically a similar trick to what I did for factorial

<s>194</s> 181

Would be nice having RegexMathEngine on TIO (=

Just want to fix a couple more bugs, and then I'll put it on TIO :)

Yay, that’s gonna make TIO links easier

@Grimy What does yours return for 0 and 1?

I make sure it correctly returns 0 for 1 (costs 2 chars)

No match for 0, but I wouldn’t consider a 0 return incorrect

In many lists, the correct answer for 1 is 1, but my version is returning 0 for 1 now

and 0 for 0

Why did you decide the correct answer for 1 is 0?

bad typo

It returns 1 for 1

As per oeis.org/…

I’m down to 151 now, do you want to see it?

Nope, I haven't golfed mine yet

Alright

151 sounds very nice though

I’m still using the fully general division from raw.githubusercontent.com/Davidebyzero/RegexGolf/master/…, but there might be a shorter way thanks to the fact that A is known to be prime.

Yeah, you can delete the (?=\2+$) because of that

Cool, 143

@Grimy BTW that's not fully generalized :) this is: regex for matching multiplication - multiplication + comparison - fully generalized.txt

I don’t see a division in there though?

@Grimy Here you go: regex for matching multiplication - division + comparison - fully generalized.txt

Heh (=

Only difference is that it handles 0, right?

Right.

shouldn’t you state the domain as ^x+\*x*=x*$ rather than ^x+\*x*=x+$ ?

Oops

@Grimy Fixed, thanks. Link is the same.

@Grimy Might as well push my ECMA+(?*) division by sqrt(2) now, because that's where the fully generalized forms came from: regex for dividing by sqrt2, with molecular lookahead.txt

Ooh base conversions

Another clever way to get around the lack of scratch space

@Grimy Hah, I finally reached 194 chars on my totient regex.

Way to go

But that was your very first try :) You seem to be much better than me at this.

Probably you can find something to golf down in my large regexes like div-by-sqrt2 and abundant numbers?

That sounds plausible, though it would take a lot of effort

@Grimy Okay, I think it's time to share our regexes. Here's mine: regex for doing Euler's totient function.txt

Here’s mine: pastebin.com/raw/MP8ByPug

The comments are pretty bad, I know =p

Mmm, you had to special-case primes

I did that at first and then found I didn't have to

Right, since you use repeated division to find the largest prime factor

I just use (x*), then assert it’s a divisor and also prime, which fails for N prime

Yay, -4 by not special-casing primes

@Grimy Yep, that's what I did in my 2014-04-08 version of largest-prime-factor

I do (?=(?:(xx+)\1*(?=\1$))*(x*)), which is the same length as your (?=((?=(xx+)(\2+$))\3)*(x*)) but uses 2 fewer capture groups, saving chars on later backrefs

Yes, I found that (?:) broke even for the first two unused captures, so I just changed them to ()

Well here it’s not a break-even, it’s strictly better

@Grimy Surely you mean -6? I get 137 from doing this to your regex

Yeah me too

The one I posted is 141

Ah yes

And then 136 by changing the (?:) to a ()

Hmm, weird, I tagged ^((?=(xx+)(\2+$))\3)*\Kx* as a later version than ^((xx+)\2*(?=\2$))*\Kx* in my collection of regexes, but the earlier version is better and is the same as what you changed it to

I didn't bother looking at the earlier versions and just grabbed the latest one to use

(of course they don't need the ^)

@Grimy May I also please see your earlier versions? 194, 181, 151, 143

One larger than 194 if you had one

194: pastebin.com/raw/sx48jAKw (doesn’t handle 1 correctly)

161: pastebin.com/raw/m2UekMb7 (that’s the last one with a loop exit condition that makes sense)

151: pastebin.com/raw/HxbGzM41

143: pastebin.com/raw/u92R47uV

Also I just got 130 with (?*)