Quick math questions

Processing
78

I got a new challenging math question and programming question. I would like to know how to find out the number of digits from numbers concatenated with a base where the counts of number is defined in base 10.

concat_consec_digits_count(n in base 10,b);

concat_consec_digits_count(23,12):
1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16-17-18-19-20-21-22-23
1-2-3-4-5-6-7-8-9-A -B -10-11-12-13-14-15-16-17-18-19-1A-1B
concat_consec_digits_count(23,12)=11+12*2=35

concat_consec_digits_count(12,5):
1-2-3-4- 5 - 6 - 7 -  8 - 9 -10-11-12
1-2-3-4- 10- 11-12 - 13 -14 -20-21-22
concat_consec_digits_count(12,5)=4*1+8*2=20

In a chatroom, someone found the answer in OEIS - A058183 - OEIS . All I need to do is to replace log_10 with log_base.

79

Is this still a challenge if you found a sequence on OEIS? Edit: I didn’t look at the sequence, but tried deriving it myself. I came up with something equivalent, though the formula on OEIS seems somewhat shorter.

After some manual inspection of such base-digit-sequences, I came up with an expression for the length L of the string of concatenated digits in base b from 1 to the largest number with n digits:

T(b,n) = \frac{1-b^n-nb^n+nb^{n+1}}{b-1}

So, for example, there are T(5,2) = 44 characters in the string “12341011121314202122232430313233344041424344” and T(3,3) = 68 characters in the string “12101112202122100101102110111112120121122200201202210211212220221222”.

To find the length S of the string for an arbitrary number N in base b, we first need to know the number of digits d for that number, which is given by:

d = \lfloor\log_b N\rfloor + 1

The length of the string is shortened by (N_\text{max}-N)d digits, where N_\text{max} is the largest number with d digits, N_\text{max} = b^d-1.

We finally have,

S(N,b,d) = T(b,d) - (b^d-1-N)d

Or, to match your definition of concat_consec_digits_count, we have after some simplification and rearrangement:

S(N,b) = N+(N+1)\lfloor\log_bN\rfloor+\frac{b\left(1-b^{\lfloor\log_bN\rfloor}\right)}{b-1}

It’s easy to verify that S(23,12) = 35 and S(12,5)=20 as in your examples.

1 Like
80

@Thanatomanic I was able to find a optimized solution for element-wise subtraction with that definition of concat_conset_digits_count. It doesn’t work if N is lower than b. This is my final formula:

concat_consec_digits_count(v)=v>=base?(
    t=floor(logb(v));
    v+(v+1)*t+(base*(1-base^t))/(base-1);
  )
  :v;

So, if v is less than base, then the answer is v, otherwise, it use that formula.

EDIT: Changed (1-base*t) to (1-base^t), and now it works for all cases.

81

Is it allowed to use a semi-colon (;) like that in the middle of a ? : expression? I’m pretty sure it was forbidden back in the days when I learned C, and we would probably have used a comma (,) instead. But maybe the C standards have evolved since then?

82

Yes. This is the G’MIC syntax.

83

ah got it, I just assumed it was C code :slight_smile:

1 Like
84

FYI, it is an expression separator, where the last assigned value is returned.

85

@Thanatomanic I found that this is wrong:

C:\Windows\System32>gmic echo {n=16;base=4;logb(n)=log(n)/log(base);n">"=base?(t=floor(logb(n));n+(n+1)*t+(base*(1-base*t))/(base-1)):n;}
[gmic]-0./ Start G'MIC interpreter.
[gmic]-0./ 40.666666666666664
[gmic]-0./ End G'MIC interpreter.

The correct is suppose to be 30.

EDIT: Oh, it was supposed to be in power function. My bad.

86

I went back to see if I can make the gradient in gmic, but this shows up as math processing error.

Edit: Now I see it in quote. Sorry about that.

I think I’m realizing the answer involve using newson-raphson method. This way I can directly map a Archimedes spiral ramp in 2D array.

87

Does anyone has any idea how the coefficient are found: How To Get A Spline's Length Using Gauss–Legendre Quadrature? | Noah Zuo's Blog

Derivative and something else, but missing something.

88

Read Gauss–Legendre quadrature - Wikipedia. See references.

89

It’s not that I want to know. It’s this part that I can’t figure out:

FVector Coeff1 = ((P0 - P1) * 2.0f + T0 + T1) * 3.0f;
FVector Coeff2 = (P1 - P0) * 6.0f - T0 * 4.0f - T1 * 2.0f;
FVector Coeff3 = T0;

Where exactly are these coming from?

90

A guess is that it describes a spline. I say that because GLQ is a means to an end, which is to calculate the length of a spline.

91

I guess I will have to resort to Gravesen. This gives me a better approximation than the UE4 approach which cannot be used due to its license.

There is a pdf here - Adaptive subdivision and the length and energy of Bézier curves - ScienceDirect

And this is the test between the UE4 and gravesen - How long is that Bézier? | Raph Levien’s blog

Still hope there is a break for me to find distance of cubic spline.

92

Here’s a challenge I have been doing for days.

Solve for n in this expression:

(sqrt(tau*n)*(n/e)^n)/(sqrt(tau*r)*(r/e)^r)*(sqrt(tau*(n-r))*((n-r)/e)^(n-r))=v

There’s an application to this. I was doing combinatories, and getting the approximate n to the gamma variation of n choose r formula which would reduce the number of loop into finding combinations with repetition given a rank. I don’t know how to use the lambert W(), and I do believe an approximation exist. If I copy 1,2,3 into y, and copy the result of n C r into x, one get something akin to a scaled logarithmic curve or LambertW() curve, so I have no reason not to believe an approximation cannot exist. The exact solution to the gamma function variation of n C r on the other hand, I don’t think it exists.

Also, Wolfram Alpha can’t solve my problem, so…

93

Neither can ChatGPT :slight_smile:

One of the several summaries presented by AI…

To solve the expression for the variable n, we need to isolate n on one side of the equation. Let’s simplify the expression step by step:

Expression: (sqrt(taun)(n/e)^n)/(sqrt(taur)(r/e)^r)(sqrt(tau(n-r))*((n-r)/e)^(n-r))

We can simplify the square roots:

sqrt(taun) / sqrt(taur) = sqrt(n/r)

Next, let’s simplify the exponentials:

(n/e)^n / (r/e)^r = (n^ne^(-n)) / (r^re^(-r)) = (n^r * (n/e)^n) / (r^r * (r/e)^r) = (n^r * n^n) / (r^r * r^r)

(sqrt(tau*(n-r))*((n-r)/e)^(n-r)) = sqrt((n-r)*tau) / ((n-r)/e)^(n-r)

Now, let’s combine all the simplified terms:

(sqrt(n/r)) * ((n^r * n^n) / (r^r * r^r)) * (sqrt((n-r)*tau) / ((n-r)/e)^(n-r))

Let’s simplify further by combining the fractions:

(sqrt(n/r)) * ((n^r * n^n * sqrt((n-r)*tau)) / (r^r * r^r * ((n-r)/e)^(n-r)))

To solve for n, we need to set the expression equal to a constant value. Let’s say the constant is C:

(sqrt(n/r)) * ((n^r * n^n * sqrt((n-r)*tau)) / (r^r * r^r * ((n-r)/e)^(n-r))) = C

At this point, the equation becomes quite complex and does not have a straightforward algebraic solution. Solving this equation for n would require numerical methods or approximation techniques.

Regenerate response

1 Like
94

Yes, I suspect it has to do with lambert W function in order to solve the equation, and the gamma version is much harder to solve. It may be that there’s no solution, but an approximation is still out there. I looked elsewhere, but there isn’t a good approximation.

95

If you can express the first derivative of your expression w.r.t. n (it seems possible at a first glance), then you may try gradient descent. That’s the simplest algorithm for doing optimization.

If you can express the second derivatives as well, then try the Levenberg-Marquardt variant, which usually converges faster.

Keep in mind that these methods works better when your function is convex (not sure that’s the case here, I’ve not checked).

96

@David_Tschumperle Thanks. I found something close, but decided to went with desmos for visual math inspection.

Here, I found something that would drastically reduce the number of loops for my g’mic command rep_r_combination_index2list: Graphing Calculator

I can change n, and the you see that it’s off by +3/+3 for 26. Which means I don’t need to do as much loops in that command.

I’m certainly adding desmos to my list of tool whenever I have to find something like this.

97

Well, the above didn’t work good.

Anyways, I have a easier math question to answer.

n is the cardinality of list of natural number.
M is the forward concatenation of n
N is the backward concatenation of n

n=123
M=1234567891011...
N=123122121....

Easy to know which is greater. Count the number of digits. In this case, At n>123, N>M until n=1000.

Note that M has 123 joined with 122 joined with 121

Once n=12345678910: 
M=123456789101112...
N=123456789101234567899..

N>M at this point. 

So, by only knowing n. How exactly do I know whether M or N is greater?